Chapter 21: The Function That Calls Itself

Learning Objectives

• Understand recursion and the call stack.
• Identify and define base cases and reduction steps.
• Comprehend tail recursion and stack overflows.
• Apply recursion to tree traversals and similar structures.

Prerequisites

Functions (Chapter 5), Call Stack.

Why Does This Exist?

Some problems, like traversing a file system or navigating trees, are naturally defined in terms of themselves. Recursion provides an elegant, concise way to express these solutions where iterative loops would be overly complex or unreadable.

History

Recursion is deeply tied to mathematical induction. In programming, it gained prominence with John McCarthy's Lisp in the late 1950s, demonstrating that you didn't always need explicit loop constructs if functions could call themselves.

Mental Model

Think of Russian nesting dolls. To find the smallest doll, you open the current one, revealing a slightly smaller version of the exact same doll, until you reach the solid one in the center (the base case). Or imagine mirrors facing each other, reflecting into infinity (except we must stop before infinity!).

Internal Working

When a function calls itself, the computer pauses the current function and creates a new "frame" on the call stack for the new call. These frames stack up until the base case is hit. Then, they resolve one by one, popping off the stack in reverse order.

Syntax

Here are classic Python recursive examples:

1def factorial(n):
2    if n == 1:  # Base Case
3        return 1
4    return n * factorial(n - 1)  # Reduction Step
5
6def fibonacci(n):
7    if n <= 1:
8        return n
9    return fibonacci(n-1) + fibonacci(n-2)

Visual Explanation

Tiny Example

1def countdown(n):
2    if n <= 0:
3        print("Liftoff!")
4        return
5    print(n)
6    countdown(n - 1)
7
8countdown(3)

Walkthrough

• Call `countdown(3)`: prints 3, calls `countdown(2)`.
• Call `countdown(2)`: prints 2, calls `countdown(1)`.
• Call `countdown(1)`: prints 1, calls `countdown(0)`.
• Call `countdown(0)`: hits base case, prints "Liftoff!", returns.
• All previous calls return in sequence.

Common Mistakes

Debugging

Print the inputs at the very start of the function, and track how they change on every call to verify you are moving toward the base case.

Mini Project

Time: 20 min.

Goal: Implement `sum_list(lst)` recursively, then calculate `sum_list([1,2,3,4,5])`.

# Recursive sum of a list
def sum_list(lst):
    # Base case: empty list has sum of 0
    if len(lst) == 0:
        return 0
    # Recursive case: first element + sum of the rest
    return lst[0] + sum_list(lst[1:])

# Test it
numbers = [1, 2, 3, 4, 5]
result = sum_list(numbers)
print(f"sum_list({numbers}) = {result}")  # 15

# Trace what happens:
# sum_list([1,2,3,4,5])
#   = 1 + sum_list([2,3,4,5])
#   = 1 + 2 + sum_list([3,4,5])
#   = 1 + 2 + 3 + sum_list([4,5])
#   = 1 + 2 + 3 + 4 + sum_list([5])
#   = 1 + 2 + 3 + 4 + 5 + sum_list([])
#   = 1 + 2 + 3 + 4 + 5 + 0  <- base case!
#   = 15
print("Stack depth was 6 frames deep (one per element + base case)")

Bigger Project

Time: 1.5 hr.

Goal: Implement Merge Sort recursively. Sort a list of 20 random numbers. Print each split and merge step.

# Merge Sort — recursive divide and conquer
import random

def merge_sort(arr, depth=0):
    indent = "  " * depth
    if len(arr) <= 1:
        print(f"{indent}BASE: {arr}")
        return arr

    mid   = len(arr) // 2
    left  = arr[:mid]
    right = arr[mid:]
    print(f"{indent}SPLIT: {arr}  →  L={left}  R={right}")

    left_sorted  = merge_sort(left,  depth + 1)
    right_sorted = merge_sort(right, depth + 1)

    merged = merge(left_sorted, right_sorted)
    print(f"{indent}MERGE: {left_sorted} + {right_sorted}  →  {merged}")
    return merged

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

random.seed(42)
data = random.sample(range(1, 50), 8)

print(f"=== Merge Sort ===  Input: {data}")
print()
sorted_data = merge_sort(data)
print(f"
Result: {sorted_data}")
print(f"O(N log N): {len(data)} items, log2({len(data)}) ≈ {len(data).bit_length()-1} levels deep")

Production Usage

File system traversal (e.g., `os.walk`), rendering DOM trees in browsers, and AI decision trees heavily rely on recursion.

Best Practices

• Always write the base case first.
• Ensure every recursive call gets closer to the base case.

Interview Questions

Revision Sheet

Connections

• Past Chapters: Functions and scoping rules.
• Future Chapters: Tree and Graph traversals.