Recursion

Some problems are convenient to describe through themselves. The factorial of a number n is the product of all numbers from 1 to n: the factorial of 5 is 1 * 2 * 3 * 4 * 5, that is, 120. It can be defined by two rules:

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

A Swift function repeats this definition word for word by calling itself:

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

print(factorial(5)) // 120

Let's go back to the food processor and see how it computes factorial(5):

1. The factorial machine got 5, but it doesn't know the answer right away.
2. It sets up an identical machine next to it, hands it 4 and waits for the result, to multiply it by 5.
3. The second machine passes the work to a third one with 3 in the same way, and so on down to the machine that got 0.
4. That last one answers 1 at once, without calling anyone.

Here the food processor picture is inaccurate. Real machines can work at the same time, but of all the calls of a function, only the newest one runs at any moment. The others wait until it returns its result.

Two kinds of branches

Recursion is a function calling itself. The compiler allows such a call: the function's name is visible inside its own body. A recursive function has branches of two kinds.

The base case

The branch in which the function finishes without a new call is called the base case. In factorial it is if n == 0 { return 1 }: the call factorial(0) returns 1 at once.

Without a base case the calls never end. Every new call must bring the argument closer to it.

The recursive step

The branch that calls the function again is called 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 up the chain, and each call multiplies what it got by its own n:

1. factorial(0) returns 1.
2. factorial(1) returns 1 * 1, that is, 1.
3. factorial(2) returns 2 * 1, that is, 2.
4. factorial(3) returns 3 * 2, that is, 6.
5. factorial(4) returns 4 * 6, that is, 24.
6. factorial(5) returns 5 * 24, that is, 120.

Common mistake

A function that adds up the numbers from 1 to n was written without a base case:

func sumTo(_ n: Int) -> Int {
    return n + sumTo(n - 1) // ✗
}

warning: function call causes an infinite recursion

The program compiles, but with a warning: the function has no branch without a new call. A warning doesn't stop the build, but treat this one as an error: such a function never returns an answer, whatever the argument. Add a base case before the recursive step: if n == 0 { return 0 }.

Key points

• Recursion is a function calling itself; a recursive function has a base case and a recursive step.
• The base case ends the function without a new call, and every new call must bring the argument closer to it.
• The results travel back up the chain: factorial(0) returns 1, and each call multiplies what it got by its own n.
• The compiler notices a function with no base case at all and warns: function call causes an infinite recursion.