Recursion and the call stack

Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. It is the natural way to write many algorithms, including merge sort, and it is the key to the two lessons that follow.

Think of a folder of documents that holds more folders. To count every file, you count the files in this folder, then do the same job in each folder inside it.

A recursive function has two parts. The base case is an input so small that the answer is known, so the function returns it without calling itself.

The recursive case calls the function on a smaller input and uses the answer. The factorial of 5 is 5 times the factorial of 4, and the factorial of 1 is 1.

# A recursive function calls itself on a smaller problem.
def factorial(n):
    if n <= 1:
        # Base case: stop here.
        return 1
    # Recursive case: n times the factorial of n - 1.
    return n * factorial(n - 1)

print(factorial(5))
# Change 5 to 10 and run again.

python3 -c "import math; print(math.factorial(10))"

When a function calls itself, the first call has not finished. It waits. Python keeps each waiting call in a stack frame on the call stack, a pile where the newest call is on top.

In the table above, four frames are on the pile at the deepest point. Then the top one returns, and the pile shrinks one frame at a time.

Each frame uses memory, so a stack cannot grow for ever. Python allows about 1000 frames by default, then raises an error called RecursionError.

A function with no base case never stops calling itself. The first Run asks for the limit. The second Run starts an endless recursion and shows the last line of the error.

python3 -c "import sys; print(sys.getrecursionlimit())"

python3 -c "exec('def f(n):\n return f(n + 1)\nf(0)')" 2>&1 | tail -n 1

The Fibonacci numbers start 0, 1, and each next one is the sum of the two before: 0, 1, 1, 2, 3, 5, 8. So fib(n) is fib(n - 1) plus fib(n - 2), and fib(0) and fib(1) are the base cases.

This function calls itself twice, so the number of calls roughly doubles each time n goes up by one.

# Fibonacci by recursion, counting how many calls it makes.
calls = [0]

def fib(n):
    calls[0] = calls[0] + 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print("fib(10) =", fib(10), "calls", calls[0])
# Change 10 to 15 and run again. Watch the calls.

printf 'def fib(n):\n    if n < 2:\n        return n\n    return fib(n - 1) + fib(n - 2)\n\nprint(fib(30))\n' > fib.py

python3 fib.py