Recursion: functions that call themselves

Why recursion?

Some problems are easiest to describe in terms of a smaller copy of themselves. The factorial of 5 is 5 times the factorial of 4. The size of a folder is the size of its files plus the size of each folder inside it. A path through a grid is one step plus a path through a smaller grid. Recursion lets you write the code exactly the way you describe the problem, and it is the base for everything else in this module: divide and conquer, backtracking and memoization. Trees (Module 7) and graphs (Module 9) use it all the time.

Base case and recursive case

A recursive function is a function that calls itself. It has two parts. The base case is an input so small that you return the answer directly, without calling again. The recursive case makes the problem smaller, calls the function on the smaller problem, and uses that answer to build its own. If the input never reaches the base case, the calls never stop.

def factorial(n):
    if n <= 1:                 # base case
        return 1
    return n * factorial(n - 1)   # recursive case: a smaller n

print(factorial(4))   # Output: 24
print(factorial(0))   # Output: 1

The call stack, step by step

When a function calls another function, the caller pauses and waits. Python keeps every paused call in a stack frame: a small record of its local variables and where to continue. The frames form the call stack, a stack in the sense of Module 4: the last call made is the first to finish. For factorial(4), four frames pile up before any multiplication happens; then they finish in reverse order.

factorial(4)                    waits for factorial(3)
  factorial(3)                  waits for factorial(2)
    factorial(2)                waits for factorial(1)
      factorial(1) returns 1    base case, the stack is 4 frames deep
    factorial(2) returns 2 * 1 = 2
  factorial(3) returns 3 * 2 = 6
factorial(4) returns 4 * 6 = 24

Time is the number of calls times the work per call: n calls with O(1) work each, so O(n). Space is the deepest the stack gets: n frames, so O(n), even though no list is created. Module 1 showed this with a recursive sum; it is true of every recursive function.

The recursion limit and RecursionError

Every frame takes memory, so Python sets a limit on how deep the stack may grow. sys.getrecursionlimit() returns 1000 by default. Going deeper raises RecursionError: maximum recursion depth exceeded. So factorial(5000) written recursively fails, while a loop handles it easily. You can raise the limit with sys.setrecursionlimit(), but very deep recursion still uses a lot of memory and can crash, so it is a last resort. JavaScript has a similar limit (in Chrome and Node.js the error is RangeError: Maximum call stack size exceeded); how deep you can go depends on the engine and the size of each frame.

Recursion or a loop?

Anything written with recursion can be written with a loop, sometimes with an explicit stack of your own. When the recursion only goes one way, like factorial or summing digits, a loop is simpler and uses O(1) space. Recursion shines when a call branches into several smaller calls (trees, subsets, divide and conquer), where the loop version needs a hand-made stack and is harder to read. In an interview, write whichever is clearer and say the depth: "this recursion goes n deep, so it uses O(n) stack space".

Tail recursion

A call is a tail call when it is the very last thing the function does, with nothing left to compute after it returns. In factorial above, the multiplication happens after the call returns, so it is not a tail call. Moving the running product into a parameter (an accumulator) makes it one. Some languages (Scheme, and many functional languages) reuse the same frame for a tail call, so tail recursion runs in O(1) space. Python never does this, by design, and most JavaScript engines (Chrome, Node.js and Firefox) do not either; Safari is the exception. So in Python, tail recursion still fails at about 1,000 levels; turn it into a loop instead.

def fact_tail(n, acc=1):
    if n <= 1:
        return acc
    return fact_tail(n - 1, acc * n)   # a tail call, but Python still adds a frame

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

print(fact_tail(5), fact_loop(5))   # Output: 120 120

How to write a recursive function

1. Say in words what the function returns, for example "count_paths(r, c) is the number of paths in an r × c grid".
2. Find the smallest inputs and their answers: these are the base cases.
3. Assume the function already works for smaller inputs (this is called the leap of faith) and build the answer for n from them.
4. Check that every recursive call moves closer to a base case.
5. Trace a tiny input by hand, then state the time (number of calls × work per call) and the space (the deepest stack).

Common mistakes

• No base case, or a base case that is never reached (for example n == 0 when n can be negative). Fix: write the base case first and check every input shrinks towards it.
• Forgetting to return the recursive result: writing factorial(n - 1) instead of return n * factorial(n - 1) gives None. Fix: every path through the function must return something.
• Hidden O(n) work in each call, such as s[1:] slicing, which copies the string. Fix: count it; pass an index instead when it matters.
• Recursing thousands of levels deep in Python. Fix: use a loop, or keep the depth near log n as in divide and conquer.
• Counting time as the depth. Fix: time is the TOTAL number of calls; a function that calls itself twice makes far more calls than its depth.