Recursion and the Call Stack

Recursion is not just elegant notation but an execution mechanism: every call creates a new frame on the call stack. Once you understand the stack you can see the time, the memory and the cause of RecursionError. This lesson deepens the introduction to recursion from the analysis and stack side.

Three ingredients

• The base case is the simplest case that stops the recursion.
• The recursive step expresses the problem through a smaller version of itself.
• Progress: every call must get closer to the base case, otherwise the recursion is infinite.

Tracing the call stack

In the factorial trace each line is a frame being created and each -> is the frame returning a value and being removed. The indentation is the depth: at fact(0) there are 4 frames on the stack.

def fact(n, depth=0):
    pad = "  " * depth
    print(f"{pad}fact({n})")
    if n == 0:
        print(f"{pad}-> 1")
        return 1
    result = n * fact(n - 1, depth + 1)
    print(f"{pad}-> {result}")
    return result

fact(3)

fact(3)
  fact(2)
    fact(1)
      fact(0)
      -> 1
    -> 1
  -> 2
-> 6

Stack size and RecursionError

CPython limits the call depth: the default sys.getrecursionlimit() is 1000. When it is exceeded a RecursionError is raised, which protects the program from overflowing the C stack and crashing.

import sys