Recursion

Jr Codex Python Notes

Level: Intermediate Prerequisites: Chapter 3 Time to complete: ~20 minutes

Table of Contents

1. What is Recursion?
2. Anatomy of a Recursive Function
3. The Call Stack, Visualized
4. Classic Example: Fibonacci
5. Recursion on Data Structures
6. Recursion vs Iteration
7. Recursion Limits & Pitfalls
8. Summary & Next Steps

1. What is Recursion?

Recursion is when a function calls itself to solve a smaller version of the same problem, until it reaches a case simple enough to answer directly.

def countdown(n):
    if n <= 0:              # base case — stops the recursion
        print("Liftoff!")
        return
    print(n)
    countdown(n - 1)          # recursive case — calls itself with a smaller problem
 
countdown(3)
# 3
# 2
# 1
# Liftoff!

Every recursive function needs exactly these two parts:

Miss the base case, or fail to move toward it, and you get infinite recursion — Python eventually raises a RecursionError.

2. Anatomy of a Recursive Function

def factorial(n):
    """n! = n * (n-1) * (n-2) * ... * 1"""
    if n <= 1:              # base case: 0! and 1! are both 1
        return 1
    return n * factorial(n - 1)   # recursive case
 
print(factorial(5))    # 5 * 4 * 3 * 2 * 1 = 120

Unwinding factorial(5)
─────────────────────────────────────────
  factorial(5) = 5 * factorial(4)
  factorial(4) = 4 * factorial(3)
  factorial(3) = 3 * factorial(2)
  factorial(2) = 2 * factorial(1)
  factorial(1) = 1                    ← base case reached, stop calling deeper

  Now it "unwinds" back up, multiplying as it returns:
  factorial(2) = 2 * 1 = 2
  factorial(3) = 3 * 2 = 6
  factorial(4) = 4 * 6 = 24
  factorial(5) = 5 * 24 = 120
─────────────────────────────────────────

3. The Call Stack, Visualized

Each recursive call adds a new frame to the call stack — Python's internal bookkeeping of "what function called what, and what do I do when it returns."

Call Stack for factorial(3)
─────────────────────────────────────────
  Growing:                    Shrinking (as each returns):
  ┌─────────────────┐          ┌─────────────────┐
  │ factorial(1)=1   │ ← top    │                  │
  ├─────────────────┤          ├─────────────────┤
  │ factorial(2)     │          │ factorial(2)=2   │ ← top
  ├─────────────────┤          ├─────────────────┤
  │ factorial(3)     │          │ factorial(3)=6   │ ← top, final answer
  └─────────────────┘          └─────────────────┘
─────────────────────────────────────────

This stack has a limit — Python's default recursion limit is 1,000 frames (see Section 7). Each unresolved call sits on the stack, consuming memory, until its base case is reached and things start "returning."

4. Classic Example: Fibonacci

def fibonacci(n):
    """Return the nth Fibonacci number (0-indexed)."""
    if n <= 1:               # base case: fib(0)=0, fib(1)=1
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)
 
for i in range(8):
    print(fibonacci(i), end=" ")
# 0 1 1 2 3 5 8 13

Warning — this naive version is exponentially slow. fibonacci(n-1) and fibonacci(n-2) each re-compute overlapping subproblems from scratch:

fibonacci(5) recomputes fibonacci(3) TWICE, fibonacci(2) THREE times, etc.
This blows up to ~2^n calls — fibonacci(35) already takes several seconds.

The standard fix is memoization — caching results you've already computed:

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fibonacci_fast(n):
    if n <= 1:
        return n
    return fibonacci_fast(n - 1) + fibonacci_fast(n - 2)
 
print(fibonacci_fast(50))    # instant, vs. the naive version which would take ages

@lru_cache is a decorator — we haven't covered those yet (Module 5), but it's worth knowing this fix exists the first time you hit slow recursion.

5. Recursion on Data Structures

Recursion is a natural fit for structures that are themselves recursively shaped — like nested lists (Module 1) or, later, trees.

def flatten(nested_list):
    """Flatten an arbitrarily nested list into a single flat list."""
    result = []
    for item in nested_list:
        if isinstance(item, list):
            result.extend(flatten(item))    # recursive case: dig into the sublist
        else:
            result.append(item)              # base case: a plain item, just add it
    return result
 
data = [1, [2, 3, [4, 5]], 6, [7, [8, [9]]]]
print(flatten(data))    # [1, 2, 3, 4, 5, 6, 7, 8, 9]

6. Recursion vs Iteration

Anything recursion can do, a loop can also do — the choice is about clarity vs. control, not capability.

# Recursive
def sum_recursive(n):
    if n == 0:
        return 0
    return n + sum_recursive(n - 1)
 
# Iterative — same result, no call-stack growth
def sum_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total
 
print(sum_recursive(5))     # 15
print(sum_iterative(5))      # 15

7. Recursion Limits & Pitfalls

import sys
print(sys.getrecursionlimit())    # 1000 by default
 
def infinite(n):
    return infinite(n + 1)         # no base case — recurses forever
 
infinite(1)     # RecursionError: maximum recursion depth exceeded

Common pitfalls:

# Pitfall 1: missing or unreachable base case
def bad_countdown(n):
    print(n)
    bad_countdown(n - 1)     # never stops — no base case at all!
 
# Pitfall 2: not moving toward the base case
def bad_factorial(n):
    if n <= 1:
        return 1
    return n * bad_factorial(n)     # ✗ should be (n - 1) — infinite recursion!

Rule of thumb: unless the problem is naturally recursive (trees, nested data, divide-and-conquer), prefer a loop in production Python — it's more memory-efficient and easier to debug.

8. Summary & Next Steps

Key Takeaways

• Every recursive function needs a base case (stops the recursion) and a recursive case (moves toward the base case).
• Each recursive call adds a frame to the call stack; Python defaults to a 1,000-frame limit (sys.getrecursionlimit()).
• Naive recursive solutions (like Fibonacci) can recompute the same subproblem many times — @functools.lru_cache fixes this via memoization.
• Recursion shines on naturally recursive structures (nested lists, trees); for simple counting/summing, iteration is usually more efficient.

Concept Check

1. What two components must every recursive function have?
2. Why is naive recursive Fibonacci exponentially slow, and what's the standard fix?
3. What error does Python raise when recursion goes too deep, and why?

Next Chapter

→ Chapter 5: Comprehensions

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index