Chapter 18: Recursion: Functions That Call Themselves

"To understand recursion, you must first understand recursion." — Anonymous (every CS professor's favorite joke)

Chapter Overview

Here's a concept that will either click immediately or feel like staring into an infinity mirror: a function that calls itself. Not another function — itself. Over and over, with smaller and smaller inputs, until it hits a stopping point and unwinds back to the original call.

This is recursion, and it's one of the most powerful — and most mind-bending — ideas in computer science. Recursion isn't just a clever trick. It's a fundamentally different way of thinking about problems. Instead of asking "how do I process all of this?", you ask "how do I process one piece of this, and can the same process handle the rest?"

If you've ever opened a set of Russian nesting dolls (matryoshka), you've experienced recursion: open the outer doll, find a smaller doll inside, open that one, find a smaller one, keep going until you reach the smallest doll that doesn't open. That smallest doll is the base case — the stopping condition. Everything before it is the recursive case — the step that makes the problem smaller and hands it off to the same process.

Or picture two mirrors facing each other. You see a reflection of a reflection of a reflection, stretching toward infinity. Recursion without a base case is exactly like that — infinite and useless. Recursion with a base case is like putting a wall behind one mirror: the reflections stop at a defined point.

By the end of this chapter, you'll be writing recursive functions that do genuinely useful things — traversing file systems, processing nested data, generating game levels — and you'll understand when recursion is the right tool and when a simple loop is better.

In this chapter, you will learn to: - Write recursive functions with proper base cases and recursive cases - Trace recursive execution through the call stack - Solve classic problems recursively (factorial, Fibonacci, string reversal, palindrome check, binary search) - Convert between recursive and iterative solutions - Understand tree recursion and its costs - Apply memoization to optimize expensive recursive calls - Recognize when recursion is the natural choice and when it isn't

Fast Track: If you've written recursive functions in another language, skim sections 18.1-18.3 and focus on 18.6 (tree recursion and memoization), 18.7 (recursive data processing), and 18.9 (thinking recursively).

Deep Dive: After this chapter, read Case Study 1 (fractals) and Case Study 2 (recursive structures in file systems and HTML). Then try the Productive Struggle problem on making change.

18.1 What Is Recursion?

Recursion is a problem-solving technique where a function solves a problem by calling itself with a smaller version of the same problem.

That definition sounds circular — and that's partly the point. Recursive solutions are circular in structure, but they're not circular in logic, because each call works on a smaller problem than the one before. Eventually, the problem gets small enough to solve directly, and the chain of calls unwinds.

Here's the simplest recursive function you'll ever see:

def countdown(n):
    """Count down from n to 1, then print 'Go!'."""
    if n <= 0:
        print("Go!")
    else:
        print(n)
        countdown(n - 1)

countdown(5)

Output:

5
4
3
2
1
Go!

Read that function carefully. When countdown(5) runs, it prints 5 and then calls countdown(4). That call prints 4 and calls countdown(3). And so on, until countdown(0) prints "Go!" and doesn't call countdown again. That's the key: eventually, the function stops calling itself.

18.1.1 The Two Essential Ingredients

Every recursive function needs exactly two things:

1. A base case: A condition where the function returns a result without calling itself. This is the smallest version of the problem — the one you can answer directly.

2. A recursive case: The part where the function calls itself with a smaller or simpler input, moving toward the base case.

Miss either one and your function breaks: - No base case? Infinite recursion (your program crashes). - No recursive case? Your function handles only the simplest input and can't solve anything else. - Recursive case doesn't make the problem smaller? Also infinite recursion.

Connection: In Chapter 6, you learned that every function call creates a new stack frame. Recursive functions create a lot of stack frames — one per call. Understanding the call stack (Section 18.3) is essential for understanding why recursion works and where it can go wrong.

18.2 Base Case and Recursive Case

Let's make these concepts concrete with the classic example: factorial.

The factorial of a positive integer n (written n!) is the product of all positive integers from 1 to n: - 5! = 5 x 4 x 3 x 2 x 1 = 120 - 3! = 3 x 2 x 1 = 6 - 1! = 1 - 0! = 1 (by mathematical convention)

Here's the insight that makes this recursive: n! = n x (n - 1)!. In other words, the factorial of 5 is 5 times the factorial of 4. The factorial of 4 is 4 times the factorial of 3. And so on, until you reach 0! = 1 — the base case.

def factorial(n):
    """Return the factorial of a non-negative integer n."""
    if n == 0:          # Base case
        return 1
    else:               # Recursive case
        return n * factorial(n - 1)

print(factorial(5))    # 120
print(factorial(0))    # 1
print(factorial(10))   # 3628800

Output:

120
1
3628800

Let's label the parts explicitly:

18.2.1 Multiple Base Cases

Some problems need more than one base case. Fibonacci (Section 18.4) needs two, because each step depends on the two previous values. And a single if can cover a whole range of base cases at once. Here's a function that recursively computes the sum of digits in a number:

def sum_of_digits(n):
    """Return the sum of digits of a non-negative integer."""
    n = abs(n)               # Handle negative input
    if n < 10:               # Base case: single digit
        return n
    else:
        return (n % 10) + sum_of_digits(n // 10)

print(sum_of_digits(1234))  # 1 + 2 + 3 + 4 = 10
print(sum_of_digits(9))     # 9
print(sum_of_digits(0))     # 0

Output:

10
9
0

The base case here is really ten base cases rolled into one: any single-digit number (0 through 9) is its own digit sum, so it's answered directly. The recursive case peels off the last digit (n % 10) and recurses on the remaining digits (n // 10). For 1234 that's 4 + sum_of_digits(123), then 3 + sum_of_digits(12), then 2 + sum_of_digits(1), and sum_of_digits(1) hits the base case.

Check Your Understanding 1: What is the base case and recursive case in the countdown function from Section 18.1? What would happen if you changed countdown(n - 1) to countdown(n)?

18.3 How Recursion Works: The Call Stack Revisited

In Chapter 6, you learned that Python maintains a call stack — a stack of frames, one per active function call. Each frame holds the function's local variables, parameters, and the return address (where to resume when the function finishes).

Recursive functions make this visible in a dramatic way: each recursive call adds a new frame to the stack. Let's trace factorial(4) step by step.

18.3.1 Building the Stack (Winding Phase)

When you call factorial(4), here's what happens:

Call 1: factorial(4) — Is 4 == 0? No. Compute 4 * factorial(3). Must wait for factorial(3) to return.

Call 2: factorial(3) — Is 3 == 0? No. Compute 3 * factorial(2). Must wait for factorial(2) to return.

Call 3: factorial(2) — Is 2 == 0? No. Compute 2 * factorial(1). Must wait for factorial(1) to return.

Call 4: factorial(1) — Is 1 == 0? No. Compute 1 * factorial(0). Must wait for factorial(0) to return.

Call 5: factorial(0) — Is 0 == 0? Yes! Return 1. (Base case reached.)

At this point, the call stack looks like this (top is the most recent call):

┌──────────────────────┐
│ factorial(0) → 1     │  ← base case, returns 1
├──────────────────────┤
│ factorial(1) waiting │  ← needs factorial(0)'s result
├──────────────────────┤
│ factorial(2) waiting │  ← needs factorial(1)'s result
├──────────────────────┤
│ factorial(3) waiting │  ← needs factorial(2)'s result
├──────────────────────┤
│ factorial(4) waiting │  ← needs factorial(3)'s result
└──────────────────────┘

18.3.2 Unwinding the Stack (Unwinding Phase)

Now the results cascade back:

• factorial(0) returns 1
• factorial(1) computes 1 * 1 = 1, returns 1
• factorial(2) computes 2 * 1 = 2, returns 2
• factorial(3) computes 3 * 2 = 6, returns 6
• factorial(4) computes 4 * 6 = 24, returns 24

Each frame pops off the stack as it returns. When the stack is empty, factorial(4) has returned 24.

18.3.3 Seeing It Yourself

You can add a print statement to watch the winding and unwinding:

def factorial_traced(n, depth=0):
    """Factorial with call stack tracing."""
    indent = "  " * depth
    print(f"{indent}factorial({n}) called")
    if n == 0:
        print(f"{indent}factorial(0) returns 1  [base case]")
        return 1
    else:
        result = n * factorial_traced(n - 1, depth + 1)
        print(f"{indent}factorial({n}) returns {result}")
        return result

factorial_traced(4)

Output:

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
        factorial(0) called
        factorial(0) returns 1  [base case]
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

The indentation shows the depth of the call stack. Notice the symmetry: the calls wind in (going deeper), hit the base case, then unwind out (returning results).

Spaced Review (Ch 6): Recall that every function call pushes a frame onto the call stack, and every return pops one off. Recursion makes this mechanism explicit — each recursive call is a full function call with its own local scope, its own copy of n, and its own return value.

18.4 Classic Recursive Problems

Recursion shines on problems that are naturally self-similar — where the problem at size n can be expressed in terms of the same problem at size n-1 (or smaller). Here are the classics that every CS student should know.

18.4.1 Fibonacci Numbers

The Fibonacci sequence is defined recursively: each number is the sum of the two preceding numbers, starting from 0 and 1.

• fib(0) = 0
• fib(1) = 1
• fib(n) = fib(n-1) + fib(n-2) for n >= 2

def fibonacci(n):
    """Return the nth Fibonacci number (naive recursive version)."""
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

for i in range(10):
    print(f"fib({i}) = {fibonacci(i)}")

Output:

fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34

This works, but it's extremely slow for large inputs. We'll see why in Section 18.6.

18.4.2 Sum of a List

You can sum a list recursively: the sum of a list is the first element plus the sum of the rest.

def recursive_sum(lst):
    """Return the sum of all numbers in a list."""
    if len(lst) == 0:       # Base case: empty list
        return 0
    else:
        return lst[0] + recursive_sum(lst[1:])

print(recursive_sum([3, 7, 1, 9, 2]))   # 22
print(recursive_sum([]))                  # 0
print(recursive_sum([42]))               # 42

Output:

22
0
42

One honest caveat: lst[1:] builds a brand-new list on every call, copying everything except the first element. For a list of n items that adds up to roughly n²/2 copied elements, so this version is O(n²) even though a loop would be O(n). It's a great way to learn the pattern; for real work, use sum(lst).

18.4.3 String Reversal

Reverse a string recursively: the reverse of a string is the last character followed by the reverse of everything except the last character.

def reverse_string(s):
    """Reverse a string recursively."""
    if len(s) <= 1:          # Base case
        return s
    else:
        return s[-1] + reverse_string(s[:-1])

print(reverse_string("hello"))     # "olleh"
print(reverse_string("Python"))    # "nohtyP"
print(reverse_string("a"))         # "a"
print(reverse_string(""))          # ""

Output:

olleh
nohtyP
a

18.4.4 Palindrome Check

A palindrome reads the same forwards and backwards. Recursively: a string is a palindrome if the first and last characters match and the middle portion is also a palindrome.

def is_palindrome(s):
    """Check if a string is a palindrome (ignoring case)."""
    s = s.lower()
    if len(s) <= 1:                   # Base case
        return True
    elif s[0] != s[-1]:              # First and last don't match
        return False
    else:
        return is_palindrome(s[1:-1])  # Check the middle

print(is_palindrome("racecar"))   # True
print(is_palindrome("hello"))     # False
print(is_palindrome("Madam"))     # True
print(is_palindrome("a"))         # True
print(is_palindrome(""))          # True

Output:

True
False
True
True
True

18.4.5 Binary Search

Binary search finds an item in a sorted list the way you find a word in a dictionary: look at the middle, decide which half the target must be in, and repeat on that half. "Repeat on that half" is the same problem on a smaller input, so the recursive version almost writes itself:

def binary_search(data, target, low=0, high=None):
    """Return the index of target in sorted list data, or -1 if absent."""
    if high is None:
        high = len(data) - 1
    if low > high:                  # Base case: empty range, not found
        return -1
    mid = (low + high) // 2
    if data[mid] == target:         # Base case: found it
        return mid
    elif data[mid] < target:        # Target can only be in the right half
        return binary_search(data, target, mid + 1, high)
    else:                           # Target can only be in the left half
        return binary_search(data, target, low, mid - 1)

scores = [62, 73, 78, 84, 88, 91, 95]
print(binary_search(scores, 88))    # 4
print(binary_search(scores, 100))   # -1

Output:

4
-1

Two details are worth noticing. First, there are two base cases: the target is found, or the range low..high is empty. Second, instead of slicing the list (which would copy it, like lst[1:] in Section 18.4.2), each call passes the indices of the half still in play. Because every call halves the range, even a list of a million items needs only about 20 calls, nowhere near Python's recursion limit. You'll write the loop version of binary search in Chapter 19.

Check Your Understanding 2: In is_palindrome, what are the base case(s)? Why does the function need two conditions that stop the recursion (length <= 1 and first != last)?

18.5 Recursion vs Iteration

Here's an important truth: every recursive solution can be rewritten as an iterative solution, and vice versa. They're equally powerful in theory. So why learn both?

Because some problems are much easier to express one way than the other. Recursion excels when the problem is naturally self-similar (like processing tree structures). Iteration excels when you're doing straightforward repetition.

18.5.1 Side by Side: Factorial

# Iterative factorial
def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Recursive factorial
def factorial_rec(n):
    if n == 0:
        return 1
    return n * factorial_rec(n - 1)

# Both produce the same result
print(factorial_iter(6))  # 720
print(factorial_rec(6))   # 720

Output:

720
720

18.5.2 Side by Side: Countdown

# Iterative countdown
def countdown_iter(n):
    while n > 0:
        print(n)
        n -= 1
    print("Go!")

# Recursive countdown
def countdown_rec(n):
    if n <= 0:
        print("Go!")
    else:
        print(n)
        countdown_rec(n - 1)

countdown_iter(3)
print("---")
countdown_rec(3)

Output:

3
2
1
Go!
---
3
2
1
Go!

18.5.3 When to Use Which

The practical rule: use recursion when the problem naturally decomposes into smaller versions of itself, especially when you're working with tree-like structures. Use iteration for everything else.

Connection (Ch 17): In Chapter 17, you learned about divide-and-conquer as an algorithmic strategy. Recursion is the natural implementation technique for divide-and-conquer algorithms — you divide the problem, recursively solve the sub-problems, and combine the results. Look back at find_max_dc in Section 17.7: it calls itself on each half of the list, and its base case is a list with one element. You were already reading recursive code.

18.6 Tree Recursion

Some recursive functions make more than one recursive call per step. This is called tree recursion because the calls branch out like a tree.

18.6.1 Fibonacci: A Tree Recursion Disaster

Look at what happens when you compute fibonacci(5):

                        fib(5)
                  /                \
             fib(4)                fib(3)
           /        \             /      \
      fib(3)        fib(2)     fib(2)    fib(1)
      /    \        /    \     /    \
  fib(2)  fib(1) fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

Count the calls: fib(3) is computed twice. fib(2) is computed three times. fib(1) is computed five times. That's 15 calls to get the answer 5. This duplication grows exponentially. Computing fib(30) makes about 2.7 million calls. fib(50) makes about 40 billion, enough to keep a typical laptop busy for somewhere between half an hour and an hour, and fib(100) would take longer than human civilization has existed.

import time

def fibonacci_slow(n):
    """Naive Fibonacci — demonstrating exponential growth."""
    if n <= 1:
        return n
    return fibonacci_slow(n - 1) + fibonacci_slow(n - 2)

# Time a few values to see the exponential blowup
for val in [10, 20, 30, 35]:
    start = time.perf_counter()
    result = fibonacci_slow(val)
    elapsed = time.perf_counter() - start
    print(f"fib({val}) = {result:>12,}  ({elapsed:.4f} seconds)")

Output (times will vary by machine):

fib(10) =           55  (0.0000 seconds)
fib(20) =        6,765  (0.0022 seconds)
fib(30) =      832,040  (0.2183 seconds)
fib(35) =    9,227,465  (2.3791 seconds)

See how the time jumps roughly tenfold with each increase of 5? Adding 1 to n multiplies the work by about 1.6, and five of those in a row multiply it by about 11. That's exponential growth. You'll usually see it written as O(2^n), a simple upper bound (the precise growth rate is about 1.618^n, the golden ratio, but either way it's exponential).

18.6.2 Memoization: Remembering Past Results

The fix is elegant: cache the results of function calls so you never compute the same value twice. This technique is called memoization (note: memo-ization, from "memo," not "memorization").

def fibonacci_memo(n, cache=None):
    """Fibonacci with memoization — O(n) time."""
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fibonacci_memo(n - 1, cache) + fibonacci_memo(n - 2, cache)
    return cache[n]

# Now it's fast even for large values
for val in [10, 20, 30, 50, 100]:
    start = time.perf_counter()
    result = fibonacci_memo(val)
    elapsed = time.perf_counter() - start
    print(f"fib({val}) = {result:>25,}  ({elapsed:.6f} seconds)")

Output (times will vary by machine):

fib(10) =                        55  (0.000007 seconds)
fib(20) =                     6,765  (0.000008 seconds)
fib(30) =                   832,040  (0.000005 seconds)
fib(50) =            12,586,269,025  (0.000008 seconds)
fib(100) = 354,224,848,179,261,915,075  (0.000022 seconds)

Instant. The naive version made 2.7 million calls for fib(30) because it kept recomputing fib(28), fib(27), and the rest over and over. The memoized version computes each of fib(2) through fib(30) exactly once, stores it in cache, and answers every repeat request with a dictionary lookup. That's about 60 calls instead of 2.7 million. The time complexity drops from exponential to O(n).

Notice the cache=None default and the if cache is None check. That's the safe pattern from Section 6.10.1: a mutable default like cache={} would be created once and silently shared between calls. Here a fresh dictionary is created for each top-level call and then passed down explicitly to every recursive call.

18.6.3 Python's Built-in Memoization: functools.cache

Python provides a decorator that does memoization for you:

from functools import cache

@cache
def fib(n):
    """Fibonacci with automatic memoization."""
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(100))   # 354224848179261915075
print(fib(200))   # 280571172992510140037611932413038677189525

Output:

354224848179261915075
280571172992510140037611932413038677189525

The @cache decorator wraps fib so that every call checks an internal dictionary first. If the argument has been seen before, it returns the cached result immediately. You write clean, simple recursive code and get memoized performance for free.

Best Practice: Use @cache (or @lru_cache for bounded caches) from functools whenever you have a pure function (same inputs always produce the same output) that gets called with the same arguments repeatedly. One catch: the arguments become dictionary keys, so they must be hashable. Numbers, strings, and tuples are fine; passing a list raises a TypeError.

18.7 Recursive Data Processing

The examples so far have been mathematical. But recursion's real power emerges when you process data structures that are inherently recursive — structures where each element can contain more elements of the same type.

18.7.1 Nested Dictionaries

Consider data organized in nested dictionaries — categories that contain subcategories that contain more subcategories:

def find_all_values(data, target_key):
    """Recursively search nested dicts for all values matching a key."""
    results = []
    if isinstance(data, dict):
        for key, value in data.items():
            if key == target_key:
                results.append(value)
            results.extend(find_all_values(value, target_key))
    elif isinstance(data, list):
        for item in data:
            results.extend(find_all_values(item, target_key))
    return results

# A nested course catalog
catalog = {
    "CS": {
        "intro": {"name": "CS 101", "credits": 3},
        "systems": {
            "name": "CS 201",
            "credits": 4,
            "labs": [
                {"name": "Networks Lab", "credits": 1},
                {"name": "OS Lab", "credits": 1},
            ],
        },
    },
    "Math": {
        "name": "Calculus I",
        "credits": 4,
    },
}

print(find_all_values(catalog, "name"))
print(find_all_values(catalog, "credits"))

Output:

['CS 101', 'CS 201', 'Networks Lab', 'OS Lab', 'Calculus I']
[3, 4, 1, 1, 4]

The function doesn't need to know how deeply nested the data is. It checks the current level, and if there's more structure underneath, it recurses. This is recursion at its most natural.

18.7.2 Directory Traversal (Dr. Patel's DNA Pipeline)

Dr. Anika Patel has thousands of DNA sequence files organized in directories by experiment, organism, and date. She needs to find every .fasta file in a directory tree that might be nested five or ten levels deep.

This is a naturally recursive problem: a directory contains files and other directories. Each of those directories contains files and other directories. The structure is self-similar.

import os

def find_files(directory, extension):
    """Recursively find all files with a given extension."""
    matches = []
    for entry in os.listdir(directory):
        full_path = os.path.join(directory, entry)
        if os.path.isfile(full_path) and entry.endswith(extension):
            matches.append(full_path)
        elif os.path.isdir(full_path):
            # Recursive case: search the subdirectory
            matches.extend(find_files(full_path, extension))
    return matches

# Example usage (works on any directory structure)
# results = find_files("/home/patel/sequences", ".fasta")
# print(f"Found {len(results)} FASTA files")

The recursive version makes the logic transparent: if it's a matching file, collect it; if it's a directory, recurse into it. For production code you'd usually reach for the standard library's os.walk(), which does the same traversal for you. Fun fact: up to Python 3.11, os.walk() was written recursively, just like this. Python 3.12 rewrote it to use an explicit stack (a list of directories still to visit), so absurdly deep folder trees no longer trigger a RecursionError (Section 18.8). Same traversal, same results, with the bookkeeping moved from the call stack into a list.

Anchor Example (Dr. Patel): Dr. Patel's sequence pipeline from earlier chapters processes files one at a time. With recursion, she can now find those files automatically, no matter how deeply nested they are. In the real world, bioinformatics pipelines routinely use recursive directory traversal to locate data files scattered across complex folder structures.

18.7.3 Flattening Nested Lists

Another common recursive problem: flattening a list that may contain sublists (which may contain sublists...):

def flatten(nested):
    """Flatten a nested list structure into a single list."""
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

data = [1, [2, 3], [4, [5, 6, [7]]], 8]
print(flatten(data))

Output:

[1, 2, 3, 4, 5, 6, 7, 8]

Try writing this iteratively. It's possible, but you'd need an explicit stack — essentially reimplementing what the call stack does automatically in the recursive version.

18.8 When Recursion Goes Wrong

Recursion's elegance comes with real hazards. Here are the most common pitfalls and how to handle them.

18.8.1 Missing Base Case: Infinite Recursion

def broken_countdown(n):
    """Missing base case — this function never stops!"""
    print(n)
    broken_countdown(n - 1)  # No if/else, no stopping condition

If you call broken_countdown(5), it prints 5, 4, 3, 2, 1, 0, -1, -2, ... forever. Except it doesn't actually run forever — Python stops it.

18.8.2 RecursionError and Stack Overflow

Python has a default recursion limit of 1,000: the call stack can hold at most about 1,000 frames at once (your module-level code takes one of them, so you actually get slightly fewer recursive calls). When a recursive function exceeds this limit, Python raises a RecursionError:

def infinite_recursion():
    return infinite_recursion()

try:
    infinite_recursion()
except RecursionError as e:
    print(f"RecursionError: {e}")

Output:

RecursionError: maximum recursion depth exceeded

This is Python protecting you from a stack overflow — when the call stack runs out of memory. Every recursive call allocates a new stack frame, and there's only so much memory available.

You can check and change the limit:

import sys

print(f"Current recursion limit: {sys.getrecursionlimit()}")

# You CAN increase it, but be cautious:
# sys.setrecursionlimit(5000)

Output:

Current recursion limit: 1000

18.8.3 Debugging Walkthrough: The Base Case Bug

Here's a function with a subtle bug. Can you spot it before reading the diagnosis?

def power(base, exponent):
    """Compute base raised to exponent recursively."""
    if exponent == 0:
        return 1
    return base * power(base, exponent - 1)

# These work:
print(power(2, 3))    # 8
print(power(5, 0))    # 1

# This crashes:
try:
    print(power(2, -1))
except RecursionError:
    print("RecursionError! Can't handle negative exponents.")

Output:

8
1
RecursionError! Can't handle negative exponents.

The bug: The base case checks exponent == 0, and the recursive case subtracts 1 from exponent. If exponent starts negative, subtracting 1 takes it further from 0, not closer. The function never reaches its base case.

The fix: Add input validation or an additional base case:

def power_fixed(base, exponent):
    """Compute base raised to exponent recursively (non-negative only)."""
    if exponent < 0:
        raise ValueError(f"Negative exponent not supported: {exponent}")
    if exponent == 0:
        return 1
    return base * power_fixed(base, exponent - 1)

print(power_fixed(2, 3))   # 8
try:
    power_fixed(2, -1)
except ValueError as e:
    print(e)                # Negative exponent not supported: -1

Output:

8
Negative exponent not supported: -1

Lesson: Always ask yourself: "Can my input reach the base case?" If there's any path where the recursive call doesn't move toward the base case, you have a bug waiting to happen.

Debugging Walkthrough: When you hit a RecursionError, add a print statement at the top of your function to show the arguments on each call. You'll immediately see whether the arguments are converging toward the base case or diverging away from it. If they're not converging, either your base case condition is wrong or your recursive step isn't making the problem smaller.

18.9 Thinking Recursively

This is the threshold concept of the chapter, and it's worth spending real time on.

18.9.1 The Leap of Faith

When students first encounter recursion, they try to trace every single call in their head. For factorial(5), that's manageable — five calls. But for fibonacci(20) or a function that traverses a directory tree with 500 folders? Tracing every call is impossible.

Here's the secret that experienced programmers know: you don't need to trace every call. Instead, you make what computer scientists call the "leap of faith":

1. Trust that the recursive call solves the smaller problem correctly. Don't think about how. Just trust it.
2. Focus on the current step. Given that the recursive call returns the right answer for the smaller problem, what do you need to do with that result to solve the current problem?
3. Make sure the base case is correct. The base case is the foundation — get it right, and the recursion builds on solid ground.

Threshold Concept: Recursive Thinking

Before: "I need to trace every recursive call to understand the code."

After: "If the base case is correct and the recursive step makes the problem smaller, the function works."

This is a genuine shift in thinking. You're moving from procedural reasoning (trace every step) to structural reasoning (verify the structure is sound). It's similar to how you trust that len() works without tracing its implementation — except now you're trusting your own function.

18.9.2 The Three-Question Test

For any recursive function, ask:

1. Is there a base case that returns a correct result without recursion?
2. Does the recursive call work on a smaller/simpler version of the problem?
3. Assuming the recursive call returns the correct result for the smaller problem, does the current step combine it correctly to solve the full problem?

If all three answers are yes, your recursive function is correct. You don't need to trace it.

18.9.3 Example: Applying the Leap of Faith

Let's design a recursive function to count the number of occurrences of a character in a string:

def count_char(s, ch):
    """Count occurrences of ch in string s."""
    if s == "":                    # Base case: empty string has 0 occurrences
        return 0
    elif s[0] == ch:
        return 1 + count_char(s[1:], ch)  # Found one; count rest
    else:
        return count_char(s[1:], ch)      # Didn't find one; count rest

print(count_char("mississippi", "s"))  # 4
print(count_char("hello", "z"))        # 0
print(count_char("", "a"))            # 0

Output:

4
0
0

Three-question test: 1. Base case: Empty string returns 0. Correct — an empty string contains 0 of anything. 2. Smaller problem: s[1:] is shorter than s by exactly one character. We'll eventually reach an empty string. 3. Current step: If the first character matches, add 1 to the count of the rest. If not, just return the count of the rest. Assuming count_char(s[1:], ch) returns the correct count for the rest of the string, this logic is sound.

The function is correct. We didn't trace a single recursive call.

Productive Struggle: Making Change

How many ways can you make change for $1.00 using pennies (1 cent), nickels (5), dimes (10), quarters (25), and half-dollars (50)?

This is a naturally recursive problem. The number of ways to make change for amount a using n kinds of coins equals: - The number of ways to make change using all n kinds of coins except the first, plus - The number of ways to make change for amount a - d using all n kinds of coins (where d is the denomination of the first kind)

Try to write a recursive function count_change(amount, coins) before looking at solutions online. Start with the base cases: what if the amount is 0? What if it's negative? What if you have no coin types left? Then build the recursive case.

This problem is challenging — it's supposed to be. Working through the struggle is where recursive thinking really develops.

18.10 Project Checkpoint: TaskFlow v1.7

In Chapter 17, you added benchmarking and algorithm analysis to TaskFlow. Now you'll add support for nested categories — categories that contain subcategories — and a recursive search that finds tasks at any depth.

The Feature

Tasks can now be organized in a hierarchy:

Work
├── Project Alpha
│   ├── Design
│   │   └── "Create wireframes" (task)
│   └── Development
│       └── "Set up CI/CD" (task)
└── Admin
    └── "File expense reports" (task)
Personal
├── "Buy groceries" (task)
└── Health
    └── "Schedule dentist" (task)

The recursive search should find tasks by keyword at any nesting level.

The Implementation

v1.7 keeps v1.5's Task dataclass exactly as it was (the full file in code/project-checkpoint.py includes it) and adds one new dataclass, Category. A category holds a list of tasks and a list of subcategories, and each subcategory is itself a Category. A data structure that contains smaller copies of itself is exactly the shape recursion is built for. Like v1.6, this checkpoint uses plain functions instead of v1.5's TaskList, so the recursion is easy to see. The listing shows the core functions; the full file adds a few more recursive helpers (search_by_priority, count_done_tasks, mark_task_done, get_all_tasks, and max_depth).

"""TaskFlow v1.7 — Recursive task search in nested categories."""

from dataclasses import dataclass, field

# Task is v1.5's dataclass, unchanged (see code/project-checkpoint.py)


@dataclass
class Category:
    """A named group of tasks that can contain smaller categories."""
    name: str
    tasks: list[Task] = field(default_factory=list)
    subcategories: list["Category"] = field(default_factory=list)


def add_task_to_category(root, category_path, task):
    """Add a task to the category at a path like 'Work/Project Alpha/Design'.

    Creates intermediate categories as needed (like mkdir -p), and records
    the path in the task's category field so the task knows where it lives.
    """
    current = root
    for part in category_path.split("/"):
        part = part.strip()
        found = None
        for sub in current.subcategories:
            if sub.name.lower() == part.lower():
                found = sub
                break
        if found is None:
            found = Category(part)
            current.subcategories.append(found)
        current = found

    task.category = category_path
    current.tasks.append(task)


def search_tasks(category, keyword, path=""):
    """Recursively search for tasks matching a keyword at any depth.

    Returns a list of (path, task) tuples.
    """
    keyword_lower = keyword.lower()
    results = []
    current_path = f"{path}/{category.name}" if path else category.name

    # Search tasks in this category
    for task in category.tasks:
        if keyword_lower in task.title.lower():
            results.append((current_path, task))

    # Recurse into subcategories
    for sub in category.subcategories:
        results.extend(search_tasks(sub, keyword, current_path))

    return results


def count_all_tasks(category):
    """Recursively count all tasks in a category tree."""
    count = len(category.tasks)
    for sub in category.subcategories:
        count += count_all_tasks(sub)
    return count


def display_tree(category, indent=0):
    """Recursively display the category tree."""
    prefix = "  " * indent
    marker = "+" if category.subcategories or category.tasks else "-"
    print(f"{prefix}{marker} {category.name}")

    for task in category.tasks:
        status = "x" if task.completed else " "
        print(f"{prefix}  [{status}] {task.title} ({task.priority})")

    for sub in category.subcategories:
        display_tree(sub, indent + 1)


# --- Demo ---
root = Category("TaskFlow")

add_task_to_category(root, "Work/Project Alpha/Design",
                     Task("Create wireframes", "high"))
add_task_to_category(root, "Work/Project Alpha/Development",
                     Task("Set up CI/CD pipeline", "high"))
add_task_to_category(root, "Work/Project Alpha/Development",
                     Task("Write unit tests", "medium"))
add_task_to_category(root, "Work/Admin",
                     Task("File expense reports", "low"))
add_task_to_category(root, "Personal/Health",
                     Task("Schedule dentist appointment", "medium"))
add_task_to_category(root, "Personal",
                     Task("Buy groceries", "high"))

# Display the full tree
print("=== TaskFlow v1.7 — Category Tree ===")
print()
display_tree(root)
print()

# Count all tasks
total = count_all_tasks(root)
print(f"Total tasks: {total}")
print()

# Recursive search
print("=== Search Results for 'ci' ===")
for path, task in search_tasks(root, "ci"):
    print(f"  [{path}] {task.title}")
print()

print("=== Search Results for 'expense' ===")
for path, task in search_tasks(root, "expense"):
    print(f"  [{path}] {task.title}")
print()

# Search for something in multiple places
print("=== Search Results for 'e' (broad search) ===")
for path, task in search_tasks(root, "e"):
    print(f"  [{path}] {task.title}")

Expected output:

=== TaskFlow v1.7 — Category Tree ===

+ TaskFlow
  + Work
    + Project Alpha
      + Design
        [ ] Create wireframes (high)
      + Development
        [ ] Set up CI/CD pipeline (high)
        [ ] Write unit tests (medium)
    + Admin
      [ ] File expense reports (low)
  + Personal
    [ ] Buy groceries (high)
    + Health
      [ ] Schedule dentist appointment (medium)

Total tasks: 6

=== Search Results for 'ci' ===
  [TaskFlow/Work/Project Alpha/Development] Set up CI/CD pipeline

=== Search Results for 'expense' ===
  [TaskFlow/Work/Admin] File expense reports

=== Search Results for 'e' (broad search) ===
  [TaskFlow/Work/Project Alpha/Design] Create wireframes
  [TaskFlow/Work/Project Alpha/Development] Set up CI/CD pipeline
  [TaskFlow/Work/Project Alpha/Development] Write unit tests
  [TaskFlow/Work/Admin] File expense reports
  [TaskFlow/Personal] Buy groceries
  [TaskFlow/Personal/Health] Schedule dentist appointment

Notice the order: within each category, the function reports that category's own tasks before recursing into its subcategories. That's why "Buy groceries" (filed directly under Personal) comes out ahead of the Health task, even though the Health category was created first.

What's Recursive Here

Three functions use recursion:

• search_tasks — searches tasks in the current category, then recurses into every subcategory. It doesn't need to know how deep the tree goes.
• count_all_tasks — counts tasks at this level, then adds the counts from all subcategories.
• display_tree — prints this category, then recursively prints each subcategory with increased indentation.

All three follow the same pattern: handle the current level, then recurse into children. The base case is implicit — when a category has no subcategories, the for sub in ... loop simply doesn't execute, and the recursion stops.

Notice what isn't recursive: add_task_to_category. It follows one known path ("Work", then "Project Alpha", then "Design"), never branching, so a plain loop does the job. Recursion earns its keep when you have to explore every branch.

Check Your Understanding 3: In search_tasks, what is the base case? It's implicit — can you state it explicitly? What would happen if a category accidentally contained itself as a subcategory?

Anchor Example: Crypts of Pythonia Dungeon Generator

The Text Adventure game can now generate dungeon maps recursively. Each room can branch into sub-rooms, creating a tree of connected rooms:

import random

def generate_dungeon(name, depth=0, max_depth=3):
    """Recursively generate a dungeon room with branching sub-rooms."""
    room = {
        "name": name,
        "treasure": random.choice([None, "gold coins", "magic scroll", "rusty key"]),
        "exits": [],
    }

    if depth < max_depth:
        num_exits = random.randint(1, 3)
        for i in range(num_exits):
            sub_name = f"{name}-{chr(65 + i)}"   # A, B, C
            sub_room = generate_dungeon(sub_name, depth + 1, max_depth)
            room["exits"].append(sub_room)

    return room


def display_dungeon(room, indent=0):
    """Recursively display the dungeon map."""
    prefix = "  " * indent
    treasure_str = f" [{room['treasure']}]" if room["treasure"] else ""
    print(f"{prefix}> {room['name']}{treasure_str}")
    for exit_room in room["exits"]:
        display_dungeon(exit_room, indent + 1)


random.seed(10)  # Same seed, same dungeon every run
dungeon = generate_dungeon("Entrance")
print("=== Crypts of Pythonia: Dungeon Map ===")
display_dungeon(dungeon)

Output (seed 10, Python 3.13; another Python version may build a different map from the same seed):

=== Crypts of Pythonia: Dungeon Map ===
> Entrance
  > Entrance-A [rusty key]
    > Entrance-A-A
      > Entrance-A-A-A [rusty key]
    > Entrance-A-B [rusty key]
      > Entrance-A-B-A [gold coins]
      > Entrance-A-B-B
    > Entrance-A-C [rusty key]
      > Entrance-A-C-A
      > Entrance-A-C-B [gold coins]
  > Entrance-B [magic scroll]
    > Entrance-B-A [rusty key]
      > Entrance-B-A-A [magic scroll]

The depth parameter controls how deep the dungeon goes. At each level, the function randomly creates 1-3 exits, and each exit leads to a recursively generated sub-room. The base case? When depth >= max_depth, the function creates a room with no exits — a dead end.

18.11 Tail Recursion (A Brief Note)

You may encounter the term tail recursion — a special form where the recursive call is the very last thing the function does:

# Tail recursive — the recursive call is the final operation
def factorial_tail(n, accumulator=1):
    if n == 0:
        return accumulator
    return factorial_tail(n - 1, n * accumulator)

print(factorial_tail(5))  # 120

Output:

120

In some languages (Scheme, Haskell, Scala), the compiler can optimize tail recursion into a loop, eliminating the stack overhead. This is called tail call optimization (TCO).

Python does not do this. Guido van Rossum, Python's creator, deliberately chose not to implement TCO. His main reasons: eliminated frames would vanish from tracebacks, making bugs harder to diagnose, and programs that came to depend on TCO would break on Python implementations that lacked it. So in Python, tail recursion has no performance advantage over regular recursion — it still uses O(n) stack space.

This is one more reason to prefer iteration in Python when dealing with simple linear recursion. Save recursion for problems where it genuinely simplifies the code — trees, nested structures, divide-and-conquer.

Chapter Summary

Recursion is a function calling itself to solve progressively smaller versions of the same problem. Every recursive function needs a base case (the stopping condition) and a recursive case (the step that makes the problem smaller). The call stack tracks each active call, and results cascade back as frames unwind.

Classic recursive problems — factorial, Fibonacci, string reversal, palindrome checking — reveal the pattern. Tree recursion (multiple recursive calls per step) can be explosively expensive, but memoization tames it by caching results. Recursion's real power shows up in naturally recursive data: nested dictionaries, directory trees, game worlds with branching paths.

The threshold concept: trust the recursion. If the base case is correct and the recursive step makes the problem smaller, the function works — you don't need to trace every call.

When recursion is right: tree structures, nested data, divide-and-conquer. When it's not: simple counting, straightforward sequences, anything where you'd exceed Python's recursion limit.

Spaced Review (Ch 14): In Chapter 14, you refactored TaskFlow into classes like Task and TaskList. A TaskList holds Task objects, but never another TaskList. Now imagine a Category class whose subcategories attribute holds more Category objects: an object that contains objects of its own type is a recursive data structure. A method such as count_tasks() would count this category's tasks and then call sub.count_tasks() on each subcategory, exactly the pattern of count_all_tasks in Section 18.10, just written as a method.

What's Next

In Chapter 19, you'll apply recursion and iteration together in searching and sorting algorithms. Merge sort — one of the most elegant algorithms in CS — is fundamentally recursive. You'll also revisit binary search, this time written as a loop, and see how the iterative version tracks the same low and high boundaries that the recursive version in Section 18.4.5 passes from call to call. The tools from this chapter will be essential.