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) - 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. 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 handles any single-digit number (0 through 9). The recursive case peels off the last digit (n % 10) and recurses on the remaining digits (n // 10).

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

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

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.

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. This duplication grows exponentially. Computing fib(30) makes over a million calls. Computing fib(50) would take longer than your lifetime.

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 roughly triples with each increase of 5? That's exponential growth — O(2^n) time complexity.

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:

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

Instant. Instead of recomputing fib(30) a million times, memoization computes it once and looks up the cached result on every subsequent call. The time complexity drops from O(2^n) to O(n).

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.

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")

This is exactly what Python's os.walk() does under the hood — it recursively traverses a directory tree. The recursive version makes the logic transparent: if it's a matching file, collect it; if it's a directory, recurse into it.

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 about 1,000 calls. When a recursive function exceeds this limit, Python raises a RecursionError:

def infinite_recursion():
    return infinite_recursion()

try:
    infinite_recursion()
except RecursionError:
    print("RecursionError: maximum recursion depth exceeded")

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
├── Health
│   └── "Schedule dentist" (task)
└── "Buy groceries" (task)

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

The Implementation

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

from datetime import datetime


def create_task(title, priority="medium"):
    """Create a new task dictionary."""
    return {
        "title": title,
        "priority": priority,
        "created": datetime.now().isoformat(),
        "done": False,
    }


def create_category(name, tasks=None, subcategories=None):
    """Create a category that can hold tasks and subcategories."""
    return {
        "name": name,
        "tasks": tasks or [],
        "subcategories": subcategories or [],
    }


def add_task_to_category(root, category_path, task):
    """Add a task to a category specified by a path like 'Work/Project Alpha/Design'."""
    parts = category_path.split("/")
    current = root

    for part in parts:
        found = None
        for sub in current["subcategories"]:
            if sub["name"].lower() == part.strip().lower():
                found = sub
                break
        if found is None:
            new_sub = create_category(part.strip())
            current["subcategories"].append(new_sub)
            found = new_sub
        current = found

    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["done"] else " "
        print(f"{prefix}  [{status}] {task['title']} ({task['priority']})")

    for sub in category["subcategories"]:
        display_tree(sub, indent + 1)


# --- Demo ---
if __name__ == "__main__":
    # Build a task hierarchy
    root = create_category("TaskFlow")

    add_task_to_category(root, "Work/Project Alpha/Design",
                         create_task("Create wireframes", "high"))
    add_task_to_category(root, "Work/Project Alpha/Development",
                         create_task("Set up CI/CD pipeline", "high"))
    add_task_to_category(root, "Work/Project Alpha/Development",
                         create_task("Write unit tests", "medium"))
    add_task_to_category(root, "Work/Admin",
                         create_task("File expense reports", "low"))
    add_task_to_category(root, "Personal/Health",
                         create_task("Schedule dentist appointment", "medium"))
    add_task_to_category(root, "Personal",
                         create_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' ===")
    results = search_tasks(root, "ci")
    for path, task in results:
        print(f"  [{path}] {task['title']}")
    print()

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

    # Search for something in multiple places
    print("=== Search Results for 'e' (broad search) ===")
    results = search_tasks(root, "e")
    for path, task in results:
        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
    + Health
      [ ] Schedule dentist appointment (medium)
    [ ] Buy groceries (high)

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/Health] Schedule dentist appointment
  [TaskFlow/Personal] Buy groceries

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.

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(42)  # For reproducible output
dungeon = generate_dungeon("Entrance")
print("=== Crypts of Pythonia: Dungeon Map ===")
display_dungeon(dungeon)

Output (with seed 42):

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

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 because it would obscure stack traces and conflict with Python's design philosophy. 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 built class hierarchies where a Task object might contain references to other Task objects. This is a recursive data structure — an object that contains references to objects of the same type. The recursive traversal patterns from this chapter apply directly to processing recursive data structures built with OOP.

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 see binary search, which divides the search space in half on every step — a divide-and-conquer strategy that recursion expresses naturally. The tools from this chapter will be essential.