Recursion and the Call Stack

Recursion is a function calling itself on a smaller version of the same problem.

Every correct recursive function has exactly two parts:

• a base case — a size small enough to answer immediately, with no further call
• a recursive case — reduces the problem and calls itself

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

Miss the base case and it never stops. Fail to make the problem smaller and it never reaches the base case. Both end the same way.

The call stack

This is the part worth slowing down for, because recursion stops feeling like magic once you can see it.

Every function call gets a stack frame holding its local variables and where to return to. Frames stack up; each returns to the one beneath.

Tracing factorial(4):

CALLS GOING DOWN                    RETURNS COMING BACK UP

factorial(4)                        4 * 6  = 24   <- final answer
  needs factorial(3)                  ^
  factorial(3)                      3 * 2  = 6
    needs factorial(2)                ^
    factorial(2)                    2 * 1  = 2
      needs factorial(1)              ^
      factorial(1) -> 1 ------------- 1   (base case, returns at once)

Four frames exist at once at the deepest point. Nothing is multiplied until the base case returns — the multiplications happen on the way back up. Students often expect the work to happen going down; it doesn't.

Stack overflow

The stack is finite. Python's default limit is about 1000 frames:

def countdown(n):
    print(n)
    countdown(n - 1)        # no base case

countdown(5)                # RecursionError after ~1000 calls

RecursionError: maximum recursion depth exceeded. That message almost always means a missing or unreachable base case.

Avoiding circularity

Circularity is recursion that fails to make progress toward the base case:

def bad(n):
    if n == 0:
        return 0
    return bad(n)           # same n — never shrinks

The base case exists but is unreachable. Three checks before you write a recursive function:

1. Is there a base case?
2. Does every recursive call move toward it?
3. Will it be reached for every valid input?

bad(5) fails check 2. factorial(-1) would fail check 3 if the base case were n == 1 instead of n <= 1 — a negative argument would count downward forever. That is why the version above uses <=.

Why use recursion at all

Not for speed — an equivalent loop is usually faster and uses no stack. Use it when the problem itself is recursive, and the code then mirrors the definition:

• Merge sort: sort each half, then merge
• Tower of Hanoi: move n−1 discs, move one, move n−1 back
• Directory trees: process each subdirectory the same way

For factorial, honestly, a loop is the better choice. It appears in teaching because it is the simplest thing on which to see the mechanism.

Recursion versus iteration

Anything expressible one way can be expressed the other — which is why the structured program theorem in Module 2 needs only three constructs and does not list recursion.