Recursion

Picture a set of Russian nesting dolls. To reach the smallest doll, you open the big one, and inside is the same doll, only smaller. You repeat the same move until you reach a solid doll that no longer opens.

Some tasks are built the same way: inside the task sits the same task, only smaller. The factorial of a number n is the product of all numbers from 1 to n. It is defined by two rules:

• the factorial of zero is 1;
• the factorial of n is n times the factorial of n - 1.

A JavaScript function repeats this definition by calling itself:

function factorial(n) {
    if (n === 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

Let's walk through how factorial(5) is computed:

1. The call factorial(5) does not know the answer at once. It calls factorial(4) and waits for the result to multiply it by 5.
2. factorial(4) hands the work to factorial(3) the same way, and so on down to factorial(0).
3. factorial(0) answers 1 at once, without calling anyone.
4. The answers travel back, and the program prints 120.

The two branches of a recursive function

Recursion is a function calling itself. Each call gets its own parameter n, so factorial(5), factorial(4) and the other calls do not interfere. A recursive function always has two branches.

The base case

factorial(0) returns 1 at once, without a new call. The branch in which the function returns without recursing is called the base case. It is the solid doll inside the set.

Without a base case the calls would never end. Each recursive call must bring the argument closer to it: here n decreases by 1.

The recursive step

The line return n * factorial(n - 1); calls the same function with an argument one smaller. The call factorial(5) waits for the result of factorial(4), which waits for factorial(3), and so on down to factorial(0).

Then the results travel back along the chain: 1, 1, 2, 6, 24 and, finally, 120. Here the nesting-doll picture stops working: a doll is only opened, while each call also returns an answer to whoever is waiting for it.

Recursion suits a task defined through a smaller copy of itself, such as a factorial or a power of a number.

The call stack

Until a call has finished, JavaScript keeps its parameters and the place to return the result to. Each unfinished call takes such a record in the call stack.

The stack is like a pile of plates:

• a new call puts a plate on top;
• a finished call takes the top plate off.

Press "Next step" and watch the pile of frames grow up to factorial(0) and then come apart from the top down. The widget computes factorial(3) so that the pile fits on the screen.

For factorial(5) the pile is taller: at the deepest point, six calls lie above the script's record, from factorial(5) down to factorial(0).

A loop instead of recursion

The size of the stack is limited. How many calls fit depends on the Node.js or browser version and on the size of each record. That is why, when the depth of recursion can reach many thousands of calls, a loop is written instead.

It does the same work without new records on the stack. The variable result accumulates the product:

function factorialLoop(n) {
    let result = 1;
    for (let i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

console.log(factorialLoop(5)); // 120

The loop calls no new functions: the variables result and i change in place. However many steps there are, the pile of plates does not grow.

Common mistake

The recursive function is called with an argument for which the base case is unreachable:

console.log(factorial(-1)); // ✗

RangeError: Maximum call stack size exceeded

This is the Node.js and Chrome message; Firefox writes InternalError: too much recursion.

From -1 the chain goes to -2, -3 and further, and n === 0 never comes. Each call adds a record until the stack is full, and the program stops with an error. Check that the base case is reachable from every valid argument, and reject invalid arguments before the recursion starts.

Interviewers like to ask this: "What happens if a recursion has no base case, or it is unreachable?" The answer: the stack overflows, and the program stops with a RangeError.

Key points

• A recursive function calls itself, and it needs a base case that returns without a new call.
• Each recursive call must bring the argument closer to the base case.
• Each unfinished call takes a record in the call stack, and the stack's size is limited.
• For very deep recursion a loop is written instead.