Key Takeaways: Recursion

One-Sentence Summary

Recursion solves problems by having a function call itself with a smaller input, bottoming out at a base case -- and the key insight is to trust the recursive call rather than trace every step.

The Two Essential Ingredients

Component What It Does What Happens Without It
Base case Stops the recursion; returns a result directly Infinite recursion, RecursionError
Recursive case Calls the function with a smaller/simpler input Function can only handle the simplest input

Recursion vs Iteration at a Glance

Factor Recursion Iteration
Best for Trees, nested data, divide-and-conquer Simple counting, accumulators, sequences
Readability Clearer for self-similar problems Clearer for straightforward repetition
Performance Stack frame overhead; O(n) memory Constant stack space; typically faster
Python limit ~1,000 calls (default) No depth limit
Python optimization No tail call optimization Python is iteration-friendly

Key Concepts

  • Recursion: A function that calls itself with progressively smaller inputs until hitting a base case.
  • Base case: The stopping condition -- the smallest problem that can be solved directly.
  • Recursive case: The step that breaks the problem down and calls the function again.
  • Tree recursion: A recursive function making multiple recursive calls per step (e.g., Fibonacci), creating exponential call growth.
  • Memoization: Caching function results to avoid redundant computation. Use @functools.cache for automatic memoization.
  • Stack overflow / RecursionError: What happens when recursion goes too deep -- Python raises RecursionError before a true stack overflow.
  • Tail recursion: When the recursive call is the last operation. Python does not optimize this.

The Leap of Faith (Threshold Concept)

Don't trace every call. Instead, verify three things: 1. The base case returns the correct result. 2. The recursive call works on a smaller problem. 3. The current step correctly combines the recursive result.

If all three are true, the function is correct.

When to Use Recursion

Use recursion when: - The data is naturally recursive (directories, trees, nested structures) - The problem decomposes into smaller self-similar sub-problems - A recursive solution is significantly clearer than an iterative one

Use iteration when: - The problem is straightforward repetition or accumulation - Deep recursion would exceed Python's stack limit - Performance is critical and the recursive overhead matters

Classic Recursive Patterns

Pattern Base Case Recursive Step
Factorial n == 0 returns 1 n * factorial(n-1)
Fibonacci n <= 1 returns n fib(n-1) + fib(n-2)
List sum empty list returns 0 first + sum(rest)
String reversal length <= 1 returns s reverse(rest) + first
Palindrome length <= 1 returns True first == last and is_palindrome(middle)
Tree traversal no children, just process current node process node, recurse on each child

Common Pitfalls

  1. Missing base case -- leads to RecursionError
  2. Base case that's never reached -- recursive step doesn't make the problem smaller
  3. Tree recursion without memoization -- exponential time (Fibonacci is the classic example)
  4. Using recursion when iteration is simpler -- e.g., summing 1 to n

What's Next

Chapter 19 uses recursion to implement merge sort -- one of the most elegant divide-and-conquer algorithms in CS. You'll also see binary search, which halves the search space recursively.