Recursion explained with factorials

TL;DR:

• A recursive function solves a problem by calling itself on a smaller version of the same problem.

• It needs a base case that stops the calls and a recursive case that moves toward the base case.

• Each call waits on the call stack until the one below it returns, then the answers multiply back up: 1, 2, 6, 24, 120.

Look up a word in a dictionary and the definition uses another word, which you look up, which uses another, until you reach a word you already know. Recursion in programming works the same way: solve a problem by reducing it to a smaller copy of itself, and stop when the problem is small enough to answer directly.

The idea in plain words

The factorial of a whole number n, written n!, is the product of all whole numbers from 1 to n. So 5! = 5 × 4 × 3 × 2 × 1 = 120. Notice that 5! = 5 × 4!, because 4! is 4 × 3 × 2 × 1. In general n! = n × (n − 1)!. The definition of a factorial contains a smaller factorial. That is recursion.

Every recursive function has two parts. The base case is an input simple enough to answer without another call. For factorial, 0! = 1. The recursive case reduces the problem and calls the function again on something smaller, then combines the result.

Why it works

Each call asks a smaller question than the one before: 5, then 4, then 3. Because the sizes keep shrinking toward the base case, the calls must eventually reach it. Then answers flow back up the chain, and each caller uses its answer to finish its own step.

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

print(factorial(5))

Worked example: 5! = 120

Run factorial(5) by hand. Going down, each call has to wait for the next.

1. factorial(5) needs 5 * factorial(4), so it waits.

2. factorial(4) needs 4 * factorial(3), so it waits.

3. factorial(3) needs 3 * factorial(2), so it waits.

4. factorial(2) needs 2 * factorial(1), so it waits.

5. factorial(1) needs 1 * factorial(0), so it waits.

6. factorial(0) is the base case and returns 1.

Now the answers come back up, in reverse order.

1. factorial(1) returns 1 * 1 = 1.

2. factorial(2) returns 2 * 1 = 2.

3. factorial(3) returns 3 * 2 = 6.

4. factorial(4) returns 4 * 6 = 24.

5. factorial(5) returns 5 * 24 = 120.

The program prints 120. The values 1, 1, 2, 6, 24, 120 are the factorials of 0 through 5, and each one is the previous one times its own number.

The call stack

The computer keeps track of the waiting calls on a call stack, a pile where the most recent call sits on top. Each call to factorial adds a layer holding its own n. At the deepest point the stack has six layers: n = 5, 4, 3, 2, 1, 0. When the base case returns, its layer is removed and the one beneath it continues. The stack empties as the answers come back.

The stack has a limit. In Python the default allows about a thousand nested calls, so very deep recursion raises a RecursionError. That is the usual symptom of a missing or unreachable base case.

The same idea with a loop, and a second recursion

Anything you can do with this kind of recursion you can do with a loop. Here is the loop version, which multiplies the numbers 2 up to n:

def factorial_loop(n):
    result = 1
    for k in range(2, n + 1):
        result = result * k
    return result

print(factorial_loop(5))

It prints 120 as well: 1 × 2 × 3 × 4 × 5. For n = 0 or n = 1 the range is empty and the answer stays 1, which agrees with the base case.

A second small recursion gives you practice at spotting the two parts. To add the numbers from 1 to n, the base case is n == 0, which gives 0, and the recursive case is n + sum_to(n − 1). For sum_to(4) the answers come back as 0, 1, 3, 6, 10, and 4 + 3 + 2 + 1 = 10.

How to check your answer

• Check the smallest cases first: factorial(0) should be 1 and factorial(1) should be 1.

• Check a case you know: factorial(3) should be 6 and factorial(5) should be 120.

• Ask whether each call moves closer to the base case. Here n drops by 1 each time.

• Count the layers: for factorial(n) there are n + 1 calls, here 6.

Common mistakes

• Forgetting the base case, so the function calls itself forever until Python raises RecursionError.

• Writing a base case that is never reached. Calling factorial(-1) here goes to −2, −3 and so on, and never hits 0.

• Calling the function with the same input instead of a smaller one.

• Forgetting to return the result of the recursive call, which makes the function return None.

• Thinking the multiplication happens on the way down. It happens on the way back up, once the answers exist.

Where you will use it next

Recursion is how merge sort and quicksort divide their work, and how programs walk through folders, trees and mazes. See it again in sorting algorithms compared. To write and test small functions of your own, read variables, loops and conditionals in Python.

Frequently asked questions

Is a loop better than recursion?

For factorial, a loop is just as clear and uses no stack. Recursion shines when the problem is naturally nested, such as folders inside folders.

Does a recursive function always need an if?

It needs some way to stop. That is usually an if that checks the base case.