Recursion

Part I · Module 11 · Chapter 11.13 · Recursion

1. A Function May Call Itself

Nothing new is required for this. Chapter 11.2 Section 6 established that a body is not executed when the def runs, so by the time the body runs, the name it refers to exists — including its own:

def countdown(n):
    if n == 0:
        return "liftoff"
    print(n)
    return countdown(n - 1)


print(countdown(3))

3
2
1
liftoff

countdown(3) printed 3 and called countdown(2), which printed 2 and called countdown(1), and so on until countdown(0) returned without calling anything.

That works, and it is a bad use of recursion. A loop does it in two lines with no call overhead and no depth limit. Section 8 returns to this; it is here first because the mechanism is easiest to see on something trivial.

2. The Two Parts

Every recursive function needs both of these, and the failures in Section 6 are what happens when one is missing:

• A base case — a condition under which it returns without calling itself. if n == 0: return "liftoff".
• A step toward the base case — each call must work on something strictly smaller. countdown(n - 1) reduces n by one every time.

Read them as a pair: when is this trivially answerable, and how do I get closer to that?

3. Each Call Has Its Own Names

The one thing worth demonstrating, because it is where intuition fails. Chapter 11.10 established that local names belong to a call — and a recursive function has several calls running at once, each with its own:

def trace(n):
    print("entering with n =", n)
    if n == 0:
        print("base case reached")
        return 0
    result = trace(n - 1)
    print("returning from n =", n, "with", result + 1)
    return result + 1


print("final:", trace(3))

entering with n = 3
entering with n = 2
entering with n = 1
entering with n = 0
base case reached
returning from n = 1 with 1
returning from n = 2 with 2
returning from n = 3 with 3
final: 3

Four calls were in progress at once. Each had its own n, and each was waiting on the one below it. When the base case returned, the waiting calls finished in reverse order — n = 1 first, n = 3 last.

4. The Shape Recursion Is For

Here is the problem that justifies the chapter. Chapter 5.7 built nested lists — a list whose items may themselves be lists:

tree = ["a", ["b", ["c", "d"]], "e"]

How deep does it go? A loop can look at the top level, but each item might be another list needing the same question asked of it, to an unknown depth. There is no number of nested loops that is enough.

def depth(items):
    if type(items) is not list:
        return 0
    deepest = 0
    for item in items:
        d = depth(item)
        if d > deepest:
            deepest = d
    return 1 + deepest


print(depth("x"))
print(depth([]))
print(depth(["a", "b"]))
print(depth(["a", ["b", ["c"]]]))

0
1
1
3

Six lines, any depth.

The base case is type(items) is not list — something that is not a list has depth 0 and is answerable immediately. The step is depth(item): each call works on an item inside the list, which is strictly smaller than the list containing it.

The body is Chapter 10.10's max-tracking accumulator, with depth(item) where a plain value would normally go. That is the only unusual thing about it.

Working through ["a", ["b", ["c"]]]:

5. Collecting While Recursing

Flattening uses the same two parts, with Chapter 10.10's list accumulator:

def flatten(items):
    result = []
    for item in items:
        if type(item) is list:
            for inner in flatten(item):
                result.append(inner)
        else:
            result.append(item)
    return result


print(flatten(["a", ["b", ["c", "d"]], "e"]))
print(flatten([]))
print(flatten([[["deep"]]]))

['a', 'b', 'c', 'd', 'e']
[]
['deep']

Note where the recursive call sits: flatten(item) returns a finished flat list, which the outer call then loops over to collect. A recursive call is an ordinary call that returns an ordinary value — Chapter 11.3's rule, unchanged.

6. Missing the Base Case

def forever(n):
    return forever(n + 1)


forever(0)

RecursionError: maximum recursion depth exceeded

There is no condition under which forever returns without calling itself, so it never stops. Python does not let it run indefinitely — it counts the calls in progress and raises once the limit is passed, around a thousand deep by default.

This is the recursive counterpart of Chapter 10.12's never-ending loop, with one important difference: a runaway loop hangs, and a runaway recursion stops with an error. The error is the friendlier failure, and it is why a missing base case is usually found in minutes.

The other version of the same mistake has a base case that is never reached:

def countdown(n):
    if n == 0:
        return "done"
    return countdown(n - 2)


print(countdown(5))

RecursionError: maximum recursion depth exceeded

5, 3, 1, -1, -3, ... steps straight past zero and continues downward forever. The base case exists and the step does not lead to it — so the rule from Section 2 needs both halves: a base case, and a step that genuinely approaches it.

7. The Depth Limit Is Real

The limit is roughly a thousand nested calls, which decides what recursion can be used for:

def count_down(n):
    if n == 0:
        return 0
    return 1 + count_down(n - 1)


print(count_down(100))
print(count_down(900))

100
900

def count_down(n):
    if n == 0:
        return 0
    return 1 + count_down(n - 1)


print(count_down(5000))

RecursionError: maximum recursion depth exceeded

Nine hundred is fine; five thousand is not. For the nested problems recursion is actually for, this is a non-issue — a directory tree a thousand levels deep does not exist. For anything proportional to the size of your data, it is disqualifying: a recursive function over a two-million-line log would fail on any real input.

8. Most Loops Should Stay Loops

The honest placement, and the reason Section 1's countdown was labelled a bad use.

Recursion costs something. Each call sets up its own names and is remembered until it returns, which is slower than a loop and bounded by the depth limit. A loop has neither cost.

Recursion is harder to read. A reader must hold several in-progress calls in their head; a loop body is read once.

Most data is flat. A list of tests, a log's lines, a dictionary of results — all handled by one loop. Recursion adds nothing.

The test is one question: does the data contain things of its own kind, to a depth I cannot know in advance? If yes, recursion. If no — and it usually is no — write the loop.

9. Predict, Run, Observe

# A
def total(n):
    if n == 0:
        return 0
    return n + total(n - 1)
print("A:", total(4))

# B
def size(items):
    if type(items) is not list:
        return 1
    n = 0
    for item in items:
        n += size(item)
    return n
print("B:", size(["a", ["b", "c"], "d"]))

# C
def depth(items):
    if type(items) is not list:
        return 0
    deepest = 0
    for item in items:
        d = depth(item)
        if d > deepest:
            deepest = d
    return 1 + deepest
print("C:", depth([[[]]]), depth("x"))

# D
def joiner(parts):
    if len(parts) == 0:
        return ""
    if len(parts) == 1:
        return parts[0]
    return parts[0] + "-" + joiner(parts[1:])
print("D:", joiner(["a", "b", "c"]))

The verified output:

A: 10
B: 4
C: 3 0
D: a-b-c

A — 4 + 3 + 2 + 1 + 0. The base case returns 0 and each call adds its own n.

B — four leaves, counted regardless of nesting. The base case returns 1 for a non-list, so the counts add up through the structure.

C — [[[]]] is three levels of list containing an empty list at the bottom, so 3. A plain string is 0.

D — the step is parts[1:], a slice (Chapter 5.2) that is one shorter every time, so it reaches the one-element base case. This is a clear recursion on flat data, and "-".join(parts) from Chapter 4.9 does it better.

10. Exercises

Exercise 1 — name the parts. For total(n) in Section 9, state the base case and the step, and say in one sentence why the step reaches the base case.

Exercise 2 — trace it. Add print statements to total(3) showing entry and exit for each call, as Section 3 does. Write down how many calls were in progress when the base case ran.

Exercise 3 — break it two ways. Write one recursive function with no base case and one whose step never reaches its base case. Record both errors and explain the difference between the two mistakes.

Exercise 4 — count the leaves. Write count_leaves(tree) returning the number of non-list items at any depth. Verify on ["a", ["b", ["c", "d"]], "e"] and on [].

Exercise 5 — deepest value. Write a function returning the maximum number found in a nested list of numbers, using the max-tracking pattern from Chapter 10.10. Verify on [1, [9, [3]], 4].

Exercise 6 — loop or recursion. For each, say which and why in one sentence: (a) total the runtimes in a flat list (b) find every .log file under a directory and its subdirectories (c) count UVM_ERROR lines (d) find the deepest nesting level in a parsed config (e) build every test-and-seed pair.

Exercise 7 — hit the limit. Write a recursive function and find roughly the largest input it survives. Say what that number means for using recursion on a two-million-line log.

Exercise 8 — rewrite it flat. Take Section 9's joiner and write the loop version, then the one-expression version using a string method you already have. Say which you would ship and why.

11. Summary

• A function may call itself, and no new rule is involved — the body runs after the name exists.
• Every recursive function needs two parts: a base case that returns without recursing, and a step that gets strictly closer to it.
• Each call has its own local names, which is Chapter 11.10's rule made visible; several calls are in progress at once.
• The shape recursion is for is data containing things of its own kind — a nested list, a directory tree, a config block of blocks — to a depth you cannot know in advance.
• A recursive call is an ordinary call returning an ordinary value, usable with the accumulator patterns from Chapter 10.10.
• No base case gives RecursionError, and so does a base case the step steps past.
• A runaway recursion errors; a runaway loop hangs. The error is the friendlier failure.
• The depth limit is about a thousand calls, which rules recursion out for anything proportional to the size of your data.
• Most loops should stay loops. Recursion is slower, harder to read, and adds nothing on flat data.
• The deciding question: does the data nest to an unknown depth? If not, write the loop.

The next chapter takes a function small enough that naming it is the longest part.