07. Recursion

Recursion is a function calling itself to solve a smaller version of the same problem. It's not a data structure — it's a problem-solving technique that underpins trees, graphs, backtracking, and dynamic programming. If you don't understand recursion, those topics will feel like magic.

The Two Parts

Every recursive function needs:

1. Base case — the trivial answer that stops recursion
2. Recursive case — break the problem into a smaller version and call yourself

def factorial(n: int) -> int:
    if n <= 1:
        return 1              # base case
    return n * factorial(n - 1)  # recursive case

Without a base case, recursion runs forever (stack overflow). Without a recursive case, you're just writing an if statement.

The Call Stack

Each recursive call pushes a new frame onto the call stack. The frame holds local variables and the return address. When the base case returns, frames pop off one by one.

factorial(4)
  → factorial(3)
    → factorial(2)
      → factorial(1)
      ← returns 1
    ← returns 2 × 1 = 2
  ← returns 3 × 2 = 6
← returns 4 × 6 = 24

Stack depth = number of nested calls. For factorial(n), depth is n.

Python's Recursion Limit

Python has a default recursion limit of 1000 frames. Hit it and you get RecursionError: maximum recursion depth exceeded.

import sys

sys.getrecursionlimit()       # 1000 (default)
sys.setrecursionlimit(10000)  # increase for deep recursion

When to increase it: tree problems with up to 10,000 nodes, DFS on large graphs, problems where the constraints guarantee deep recursion.

When NOT to increase it: if recursion depth could be millions, convert to iteration instead. Python doesn't optimize tail recursion — each frame costs real memory (~50-100 bytes).

The Recursive Leap of Faith

Don't trace every call mentally. Instead, trust that the recursive call returns the correct answer for the smaller problem, then use that to build the answer for the current problem.

def sum_list(nums: list[int]) -> int:
    if not nums:
        return 0                          # base case
    return nums[0] + sum_list(nums[1:])   # first + sum of rest

You don't need to trace sum_list([1,2,3,4]) → sum_list([2,3,4]) → ... Just trust: "if sum_list(nums[1:]) gives me the sum of everything except the first element, then adding nums[0] gives me the total."

Recursion on Trees

Trees are naturally recursive — every subtree is itself a tree. This is why most tree problems use recursion.

LeetCode 104 - Maximum Depth of Binary Tree

def max_depth(root) -> int:
    if not root:
        return 0  # base case: empty tree has depth 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

The pattern: handle None (base case), then combine results from left and right subtrees.

Recursion on Linked Lists

LeetCode 206 - Reverse Linked List (Recursive)

def reverse_list(head):
    if not head or not head.next:
        return head                   # base case: 0 or 1 node
    new_head = reverse_list(head.next)  # reverse the rest
    head.next.next = head              # point next node back to me
    head.next = None                   # I'm now the tail
    return new_head

LeetCode 21 - Merge Two Sorted Lists (Recursive)

def merge_two_lists(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1
    if list1.val <= list2.val:
        list1.next = merge_two_lists(list1.next, list2)
        return list1
    else:
        list2.next = merge_two_lists(list1, list2.next)
        return list2

Each call attaches the smaller node and recurses on the remaining lists. Base case: one list is empty, return the other.

Multiple Recursive Calls

Some problems make more than one recursive call per frame. This creates a tree of calls.

# Fibonacci — two recursive calls per frame
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # O(2ⁿ) without memoization!

Two calls per level means exponential growth. This is where memoization comes in.

Memoization with functools.cache

Python makes memoization trivial with decorators. @cache stores results of previous calls — turning O(2ⁿ) into O(n).

from functools import cache

@cache
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)  # O(n) with memoization

fib(100)  # instant — no repeated work

@cache is unbounded (stores every result forever). Use @lru_cache(maxsize=None) for the same behavior, or @lru_cache(maxsize=128) to limit memory:

from functools import lru_cache

@lru_cache(maxsize=None)
def climb_stairs(n: int) -> int:
    if n <= 2:
        return n
    return climb_stairs(n - 1) + climb_stairs(n - 2)

Important: @cache and @lru_cache only work with hashable arguments (ints, strings, tuples). If you need to pass a list, convert it to a tuple first.

@cache
def helper(nums: tuple, target: int) -> int:
    ...

# Call with: helper(tuple(nums), target)

Recursion vs Iteration

Any recursion can be converted to iteration using an explicit stack. Recursion is often cleaner for tree/graph problems; iteration avoids RecursionError for deep problems.

# Recursive DFS
def dfs(node):
    if not node:
        return
    print(node.val)
    dfs(node.left)
    dfs(node.right)

# Iterative equivalent
def dfs_iterative(root):
    stack = [root]
    while stack:
        node = stack.pop()
        if not node:
            continue
        print(node.val)
        stack.append(node.right)
        stack.append(node.left)

When to use recursion: tree problems, divide-and-conquer, backtracking, when the recursive solution is clearer.

When to use iteration: deep recursion (risk of RecursionError), performance-critical code, simple loops.

Backtracking Template

Backtracking is recursion with undo. Try a choice, recurse, undo the choice, try the next.

LeetCode 22 - Generate Parentheses

def generate_parenthesis(n: int) -> list[str]:
    result = []

    def backtrack(curr: list[str], open_count: int, close_count: int):
        if len(curr) == 2 * n:
            result.append("".join(curr))
            return
        if open_count < n:
            curr.append("(")
            backtrack(curr, open_count + 1, close_count)
            curr.pop()  # undo
        if close_count < open_count:
            curr.append(")")
            backtrack(curr, open_count, close_count + 1)
            curr.pop()  # undo

    backtrack([], 0, 0)
    return result

Common Mistakes

1. Missing base case — infinite recursion, RecursionError
2. Base case doesn't cover all terminal states — e.g., checking n == 0 but not n < 0
3. Not making the problem smaller — recursive call must move toward the base case
4. Forgetting @cache arguments must be hashable — lists aren't hashable, use tuples
5. Not increasing recursion limit when constraints require depth > 1000

Practice Problems

Key Takeaways

• Every recursive function needs a base case (stop) and a recursive case (shrink and call)
• The call stack tracks each frame — Python's default limit is 1000, increase with sys.setrecursionlimit()
• Use the recursive leap of faith: trust the recursive call works, build on its result
• Trees are naturally recursive — most tree solutions follow: handle None, combine left + right
• @functools.cache turns exponential recursion into linear time — Python's killer feature for DP
• Only hashable arguments work with @cache — convert lists to tuples
• Any recursion can become iteration with an explicit stack
• Recursion is the foundation for trees, graphs, backtracking, and DP