Recursion Fundamentals

The Nesting Doll

Picture a set of Matryoshka dolls — the famous Russian nesting dolls. You hold the largest one in your hand. You open it. Inside is a slightly smaller doll. You open that one. Inside is another. And another. Until finally you reach the smallest doll, a solid piece of wood that contains nothing.

To find the innermost doll, you follow a pattern:

1. Open the current doll
2. If it contains a doll, repeat with the inner doll
3. If it contains nothing, you're done — start coming back out

That's recursion. A problem defined in terms of a smaller version of itself, applied repeatedly until you reach a point simple enough to answer directly.

Every recursive algorithm has this same DNA. And understanding that DNA is the key to writing — and reading — recursive code fluently.

The Two Required Parts

Every recursive function MUST have exactly these two things:

1. Base Case — When to Stop

The base case is the simplest version of the problem, one you can answer directly without recursing further. It's the solid innermost doll.

Without a base case, the function calls itself forever — a stack overflow.

2. Recursive Case — How to Reduce

The recursive case breaks the current problem into a smaller version of the same problem, then calls itself on that smaller version.

The key rule: each recursive call must move closer to the base case.

How Recursion Works: The Call Stack

When a function calls itself, Python (and every language) uses a call stack — a pile of active function frames.

factorial(4)
  └── factorial(3)
        └── factorial(2)
              └── factorial(1)
                    └── returns 1  ← base case
              returns 1 * 1 = 1
        returns 2 * 1 = 2
  returns 3 * 2 = 6
returns 4 * 6 = 24

Each frame holds that call's local variables and waits while inner calls resolve. When the base case returns, the stack unwinds — each frame uses its inner call's result to compute and return its own result.

Classic Recursive Implementations

Factorial (n!)

def factorial(n):
    # Base case: 0! = 1 and 1! = 1
    if n <= 1:
        return 1
    # Recursive case: n! = n * (n-1)!
    return n * factorial(n - 1)

print(factorial(5))
# Output: 120

Execution trace for 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
             = 2 * 1 = 2
             = 3 * 2 = 6
             = 4 * 6 = 24
             = 5 * 24 = 120

Complexity: O(n) time, O(n) space (n stack frames)

Fibonacci Sequence (Naive Recursive)

def fib(n):
    # Base cases
    if n == 0: return 0
    if n == 1: return 1
    # Recursive case
    return fib(n - 1) + fib(n - 2)

print(fib(6))
# Output: 8
# Sequence: 0, 1, 1, 2, 3, 5, 8, ...

WHY IT'S SLOW — the problem:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) → 1
│   │   │   └── fib(0) → 0
│   │   └── fib(1) → 1
│   └── fib(2)           ← REPEATED WORK
│       ├── fib(1) → 1
│       └── fib(0) → 0
└── fib(3)               ← REPEATED AGAIN
    ├── fib(2)
    │   ├── fib(1) → 1
    │   └── fib(0) → 0
    └── fib(1) → 1

fib(3) is computed twice, fib(2) is computed three times. For fib(50), this explodes to O(2ⁿ) — over a trillion operations. This motivates memoization (dynamic programming), covered in a later lesson.

Sum of a List

def sum_list(arr):
    # Base case: empty list sums to 0
    if len(arr) == 0:
        return 0
    # Recursive case: first element + sum of rest
    return arr[0] + sum_list(arr[1:])

print(sum_list([1, 2, 3, 4, 5]))
# Output: 15

Trace:

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 = 15

Power Function

def power(base, exp):
    # Base case: anything to the power 0 is 1
    if exp == 0:
        return 1
    # Recursive case: base^exp = base * base^(exp-1)
    return base * power(base, exp - 1)

print(power(2, 8))
# Output: 256

Bonus insight: A smarter version halves the exponent each step — base^exp = (base^(exp//2))² — reducing this to O(log n) time. This is called fast exponentiation.

The Danger: Stack Overflow

def infinite_recursion(n):
    return infinite_recursion(n + 1)   # No base case!

infinite_recursion(0)
# RecursionError: maximum recursion depth exceeded

Python's default recursion limit is 1000 frames. Exceed it and your program crashes. This is why every recursive function must have a base case that is always reachable.

Common mistake — base case exists but is never reached:

def countdown(n):
    if n == 0: return      # base case
    return countdown(n + 1)  # Bug: goes UP, never reaches 0

Recursion vs. Iteration

Any recursive function can be rewritten iteratively (using an explicit stack). Some are much cleaner recursively.

When Recursion Is the Natural Choice

Recursion shines when the data structure itself is recursive:

Binary Tree:           Directory system:
     5                 /home
    / \               ├── user/
   3   8             │   ├── docs/
  / \   \            │   └── photos/
 1   4   9           └── tmp/

Both a binary tree and a file system are defined as: a node containing smaller nodes of the same type. Recursive traversal writes itself almost automatically.

def tree_sum(node):
    if node is None:             # base case: empty node
        return 0
    return node.val + tree_sum(node.left) + tree_sum(node.right)

This would take a complex loop with an explicit stack to replicate iteratively.

The "Leap of Faith" Method

When writing a recursive function, don't try to mentally trace every call. Instead:

1. Define clearly what your function does (its contract)
2. Write the base case — the simplest possible input
3. Assume it works for a smaller input (the leap of faith)
4. Use that result to build the answer for the current input

For factorial(n):

• Contract: returns n!
• Base: if n <= 1: return 1
• Leap of faith: assume factorial(n-1) correctly returns (n-1)!
• Build: return n * factorial(n-1)

Trust the recursion. The math handles the rest.

Key Takeaways

• Recursion = a function that calls itself with a smaller version of the problem
• Every recursive function needs a base case (stop condition) and a recursive case (reduction step)
• Recursion uses the call stack — each call waits for inner calls to return
• Naive fibonacci is O(2ⁿ) because it recomputes the same subproblems — this motivates memoization
• Recursion is most natural for trees, graphs, and divide-and-conquer algorithms
• Use the "leap of faith" method: trust your function works for n-1, use it to solve n

Next lesson: Backtracking — recursion with the power to undo decisions.