Recursion | Learn to Write Code

A recursive action calls itself

Recursion is a function calling itself to solve a smaller version of the same problem.

Every recursive action needs a base case: a condition simple enough to answer directly, without calling itself again. Without one, the calls would never stop.

Every recursive ACTION needs a base case that stops it.
Each call should work on a smaller version of the problem.
Without a base case, recursion repeats forever, like a loop with no stopping condition.
It is another way to repeat work, alongside loops.

Think of Russian nesting dolls: each doll contains a smaller version of itself, until you reach the smallest one that does not open.

Try it: What is the base case in CalculateFactorial, and what would happen if you removed it?

CalculateFactorial calls itself on a smaller number

When number is 1 or less, the base case sends 1 back directly. Otherwise the action calls itself with a smaller number first.

Pseudocode

ACTION CalculateFactorial WITH number
    IF number LESS OR EQUAL TO 1 THEN
        SEND 1 BACK
    END IF

    CREATE smallerResult AS CALL ACTION CalculateFactorial WITH number - 1
    SEND number * smallerResult BACK
END ACTION

CREATE result AS CALL ACTION CalculateFactorial WITH 5
SHOW result

The same idea in Python

Python functions can call themselves by name, the same as any other function call.

Python

def calculateFactorial(number):
    if number <= 1:
        return 1

    smallerResult = calculateFactorial(number - 1)
    return number * smallerResult

result = calculateFactorial(5)
print(result)

The same idea in JavaScript

A named JavaScript function can call itself the same way it would call any other function.

JavaScript

function calculateFactorial(number) {
    if (number <= 1) {
        return 1;
    }

    const smallerResult = calculateFactorial(number - 1);
    return number * smallerResult;
}

const result = calculateFactorial(5);
console.log(result);

The same idea in C#

A C# method can call itself the same way it would call any other method.

static int CalculateFactorial(int number)
{
    if (number <= 1)
    {
        return 1;
    }

    int smallerResult = CalculateFactorial(number - 1);
    return number * smallerResult;
}

int result = CalculateFactorial(5);
Console.WriteLine(result);

The same idea in Java

A Java method can call itself the same way it would call any other method.

Java

static int calculateFactorial(int number) {
    if (number <= 1) {
        return 1;
    }

    int smallerResult = calculateFactorial(number - 1);
    return number * smallerResult;
}

int result = calculateFactorial(5);
System.out.println(result);

The same idea in C++

A C++ function can call itself the same way it would call any other function.

C++

int calculateFactorial(int number)
{
    if (number <= 1)
    {
        return 1;
    }

    int smallerResult = calculateFactorial(number - 1);
    return number * smallerResult;
}

int result = calculateFactorial(5);
std::cout << result << '\n';