lesson 175 Algorithms & Complexity · advanced

Recursion trade-offs: depth and repeated work

Recursion is a natural fit for nested data, but every call costs a frame on Python's call stack, and a recursion that repeats subproblems can explode. Loops and explicit stacks avoid both.

You'll be able to

Count the calls a recursive function makes and spot exponential repetition
Explain RecursionError and the default limit of about 1,000 frames
Rewrite a recursive tree walk as a loop with an explicit stack

The idea

In the Advanced Functions & Recursion module a function called itself until a base case. Two costs come with that. First, a function that calls itself twice per step can solve the same small problem over and over. Counting the calls shows it: the number of ways to climb a staircase taking 1 or 2 steps at a time is the ways for one step less plus the ways for two steps less.

Run each example to see what it prints. Running examples doesn't count toward progress.

example-1.py · Counting the calls

counter = {"calls": 0}

def ways(steps):
    counter["calls"] += 1
    if steps <= 1:
        return 1
    return ways(steps - 1) + ways(steps - 2)

for n in [10, 20, 25]:
    counter["calls"] = 0
    print(n, ways(n), counter["calls"])

Second, every call that hasn't returned yet keeps a frame (its local variables and where to continue) on the interpreter's call stack. CPython stops at about 1,000 frames by default (sys.getrecursionlimit()) and raises RecursionError rather than run out of memory. Nested data from the outside world (a comment thread, a folder tree, a JSON document) can easily be deeper than that.

example-2.py · A reply chain 1,200 levels deep

def count_comments(comment):
    total = 1
    for reply in comment["replies"]:
        total += count_comments(reply)
    return total

thread = {"text": "first", "replies": []}
current = thread
for n in range(1200):
    reply = {"text": f"reply {n}", "replies": []}
    current["replies"].append(reply)
    current = reply
print(count_comments(thread))

The fix is to keep the stack yourself. A recursive walk remembers *what is left to visit* in its frames; a loop can remember the same thing in a list used as a stack (“Stacks and queues”), which is limited only by memory.

example-3.py · Folder sizes with an explicit stack

def folder_size(folder):
    total = 0
    stack = [folder]
    while stack:
        current = stack.pop()
        total += current["size"]
        for child in current["children"]:
            stack.append(child)
    return total

project = {"size": 4, "children": [
    {"size": 120, "children": []},
    {"size": 8, "children": [{"size": 300, "children": []}]},
]}
print(folder_size(project))

deep = {"size": 1, "children": []}
current = deep
for n in range(1200):
    child = {"size": 1, "children": []}
    current["children"].append(child)
    current = child
print(folder_size(deep))

When to use what: recursion is clear and fine when the depth is small and known (a menu three levels deep, a balanced tree) and each subproblem is solved once. Switch to a loop when subproblems repeat (keep earlier answers, as the try-it does) or when the depth comes from data you don't control. The Profiling & Optimization module shows a third option, caching results. Mistakes to avoid: a missing or unreachable base case (infinite recursion ends in RecursionError), and raising the recursion limit instead of fixing the algorithm.

Review

Count calls: a function that calls itself twice per step on overlapping problems does exponential work.
Each pending call is a frame; past about 1,000 (sys.getrecursionlimit()) Python raises RecursionError.
A loop that keeps earlier answers removes repetition; a list used as a stack removes the depth limit.
Next module: what all these objects cost in memory, and how CPython manages it.

Practise this

Evaluate a deeply nested formula without recursion