Recursion & the Call Stack

What is recursion?

A function is recursive when it solves a problem by calling itself on a smaller version of the same problem:

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

Every recursive function has two parts:

1. Base case: a version small enough to answer directly (here n ≤ 1).
2. Recursive case: reduce the problem and call yourself, getting closer to the base case.

The call stack

When a function is called, the computer pushes a stack frame onto the call stack. The frame holds that call’s own parameters and local variables, plus the place in the caller to continue at when it returns. When the call returns, its frame is popped.

For factorial(5) the stack grows to 5 frames:

Step	Stack (top on the right)	What happens
1	f(5)	f(5) needs f(4)
2	f(5) f(4)	f(4) needs f(3)
3	f(5) f(4) f(3)	…
5	f(5) f(4) f(3) f(2) f(1)	f(1) is the base case: returns 1
6	f(5) f(4) f(3) f(2)	f(2) = 2 × 1 = 2
9	(empty)	f(5) = 5 × 24 = 120

The stack is last in, first out (stack): the deepest call finishes first. Each frame has its own n, which is why the calls do not overwrite each other.

When recursion branches: Fibonacci

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Now each call makes two calls, and the calls form a tree. fib(5) makes 15 calls, although only 6 different values (fib(0) … fib(5)) exist: fib(3) is computed twice, fib(2) three times. fib(20) makes 21,891 calls. The work grows like 1.6ⁿ.

Yet the stack is never deeper than about n frames: the computer walks the tree depth-first, and only one path from the root is on the stack at any moment.

Memoisation

Store each answer the first time it is computed, and look it up afterwards:

def fib(n, memo={}):
    if n in memo:
        return memo[n]
    memo[n] = n if n < 2 else fib(n - 1) + fib(n - 2)
    return memo[n]

The pink nodes in the model are memo hits: they return immediately with no subtree below them. fib(20) now needs 39 calls instead of 21,891. This is the top-down form of dynamic programming.

Stack overflow

The call stack has a limited size. Python allows about 1000 frames by default (sys.getrecursionlimit()); calling factorial(100000) raises a RecursionError. In C or C++ a too-deep recursion crashes the program with a stack overflow.

Any recursion can be rewritten with a loop and an explicit stack that you manage yourself, which is what the computer does behind the scenes. Simple recursions like factorial (tail recursion) become a plain loop.

When to use recursion

Good fit	Better as a loop
Trees and nested data (traversals, file systems, JSON)	Simple counting (factorial, sum of a list)
Divide and conquer (merge sort, quick sort)	Very deep recursion (thousands of levels)
Backtracking (N-queens, sudoku)	Fibonacci without memoisation

The running time of a recursive algorithm is described by a recurrence; see recurrences and the master theorem.

Code

import sys

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

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)  # two recursive calls: a tree of calls

memo_calls = 0
def fib_memo(n, memo={}):
    global memo_calls
    memo_calls += 1
    if n in memo:
        return memo[n]              # computed before: no further calls
    memo[n] = n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]

def factorial_with_own_stack(n):
    """The same computation without recursion: we manage the 'call stack' ourselves."""
    stack = []
    while n > 1:                    # the 'calls': push the pending multiplications
        stack.append(n)
        n -= 1
    result = 1                      # the base case
    while stack:                    # the 'returns': pop in reverse order
        result *= stack.pop()
    return result

print(factorial(5), factorial_with_own_stack(5))
# 120 120
print(fib(5), 'calls:', calls)
# 5 calls: 15
calls = 0
print(fib(20), 'calls:', calls)
# 6765 calls: 21891
print(fib_memo(20), 'calls with memo:', memo_calls)
# 6765 calls with memo: 39
print('recursion limit:', sys.getrecursionlimit())
# recursion limit: 1000
try:
    factorial(100_000)
except RecursionError as e:
    print('RecursionError:', e)
# RecursionError: maximum recursion depth exceeded (the exact wording depends on the Python version)

Common mistakes

• Forgetting the base case, or writing one that is never reached (for example factorial(n + 1)).
• Thinking all calls share one n. Each frame has its own copy.
• Ignoring the memory cost. Recursion uses O(depth) stack space even when no variable looks big.
• Using plain recursion for overlapping subproblems. Add memoisation or use a loop.
• Recursing on huge inputs in Python. The default limit of about 1000 frames is reached quickly.