The call stack

In the previous lesson, the factorial food processor computed the factorial as a chain. Each machine got its own number, passed the work to its neighbor and waited for the answer. While a machine waits, its number stays inside it, and the neighbors don't touch it.

Let's look at this function once more:

func factorial(_ n: Int) -> Int {
    if n == 0 {
        return 1
    }
    return n * factorial(n - 1)
}

print(factorial(5)) // 120

By the time the program reaches factorial(0), none of the six calls has finished: factorial(5) waits for the result of factorial(4), which waits for factorial(3), and so on. They all have the same parameter, n, but six values, from 5 down to 0. Where does the program keep all these n values, and why don't they get mixed up?

Each call has its own box

Each call gets its own box with its parameters and variables. The box of the call factorial(5) holds n equal to 5, and the box of factorial(4) holds its own n equal to 4. One name, but six different boxes.

Here the food processor picture stops working: you would need six real machines, while the program has one function. What is kept separately for each call is only its box of data and the place to return the result to.

A stack of boxes

Until a call finishes, its box is kept in memory. This memory area is called the call stack: a new call puts a box on top, and a finished call takes the top box off. That is what "stack" means: as with a stack of plates, you add and remove only at the top.

The call whose box lies on top is always the one running, and the ones below it wait.

Press "Next step" and watch the column of boxes: it grows up to factorial(0), and then the boxes come off from the top. To fit the column on the screen, this one computes factorial(3).

The main thing the widget shows: all the boxes have the same name n, but different values, and no call touches another call's n.

Stack overflow

Interviewers often ask this: what happens if recursion never stops? The answer has three parts:

• every unfinished call keeps its box on the call stack;
• the memory for the stack is limited, and endless recursion uses it up, which is called a stack overflow;
• the program crashes.

A loop instead of recursion

The same factorial can be computed with a loop:

func factorialLoop(_ n: Int) -> Int {
    var result = 1
    for i in stride(from: 2, through: n, by: 1) {
        result *= i
    }
    return result
}

print(factorialLoop(5)) // 120

The loop makes no new calls: the variable result changes in place, and the stack does not grow. The numbers come from stride here, not from the range 2...n: with n below 2, that range would crash the program. The stride sequence is empty in that case, and the function returns 1.

Recursion repeats the definition word for word, while a loop uses less memory. When there can be tens of thousands of calls or more, you choose a loop.

Common mistake

A recursive function was called with an argument from which the base case cannot be reached:

print(factorial(-1)) // ✗

The program compiles, but crashes when it runs. n becomes -2, -3 and so on, never reaching zero, and the boxes pile up until the stack's memory runs out. There is no Fatal error line here: the program stops on a memory access error.

If a function has no base case at all, the compiler notices it on its own and warns. But it cannot see an unreachable base case. Let the base case catch every value at which the recursion must stop: with the condition n <= 0 instead of n == 0, the call factorial(-1) returns 1 instead of crashing the program.

Key points

• Each call has its own box with its parameters, so the calls of one function don't mix up their n.
• The boxes lie on the call stack: a new call puts its box on top, and a finished call takes the top one off.
• The stack's memory is limited: if the base case cannot be reached, as with factorial(-1), the stack overflows, and the program crashes.
• A loop makes no new calls, and the stack does not grow, so for tens of thousands of repetitions you choose a loop.