Chapter 11: Recursion

1. What is Recursion?

Imagine standing between two mirrors: you see a reflection inside a reflection, getting smaller each time. In programming, recursion is similar— a function keeps calling itself, each time working on a tinier version of the original problem, until it reaches a case so small it can finish immediately.

2. Two Rules Every Recursive Function Follows

If a base case is missing or never reached, the calls never stop and you get a stack overflow error.

3. Three Flavors of Recursion

Tip: Python does not automatically optimize tail recursion, but the style can still make intent clearer.

4. Worked-Through Examples

A. Sum from 1 to n

def sum_to_n(n):
    if n == 0:        # base
        return 0
    return n + sum_to_n(n-1)   # recursive

Call flow for n = 3

sum_to_n(3)
 └─ 3 + sum_to_n(2)
      └─ 2 + sum_to_n(1)
           └─ 1 + sum_to_n(0)
                └─ 0   ← base case

Then results bubble back: 0 → 1 → 3 → 6.

B. Factorial (direct recursion) 5! = 5 × 4 × 3 × 2 × 1

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)

C. Even / Odd (indirect recursion)

def is_even(n):
    if n == 0: return True
    return is_odd(n-1)

def is_odd(n):
    if n == 0: return False
    return is_even(n-1)

Each call shrinks n by 1, so one of them will eventually reach 0.

D. Tail-recursive Factorial

def fact_tail(n, acc=1):
    if n <= 1:
        return acc
    return fact_tail(n-1, n*acc)

All the “work” is stored in acc, so the last thing done is the call itself.

E. Fibonacci

Plain recursive Fibonacci mirrors the definition F(n) = F(n-1) + F(n-2) with F(0)=0, F(1)=1.

⚠️ Note: This naive version repeats work and grows exponentially slow. For bigger n use memoization (caching) or an iterative loop.

F. Binary Search

Recursion fits naturally because each step cuts the list in half. Base cases are “found it” or “ran out of space”.

G. Greatest Common Divisor (GCD)

The Euclidean algorithm: gcd(a, b) = gcd(b, a % b) until b == 0. Each step shrinks one argument, so it converges quickly.

H. List & String Tricks

• List sum / list reverse
• String reverse / palindrome check

These all follow the same pattern: peel off one element/character, solve the rest recursively, then combine.

5. When to Choose Recursion

6. Best Practices Checklist ✔️

1. Clear base case—guarantee a stop.
2. Progress toward base every call.
3. Understand cost: each call adds a stack frame (memory).
4. Consider alternatives: tail recursion, memoization, or iterative loops.
5. Test with small inputs first—they’re easier to debug and trace.

7. Big-O at a Glance

8. Key Takeaway

Recursion is just “a problem solving itself with less baggage each time.” If you can (1) state a simple base case and (2) shrink the problem on every step, you have a safe, elegant solution.