Recursion

A function is recursive when it calls itself. Every recursive function needs a base case (when to stop) and a recursive case (how to break the problem down).

Why It Matters

Recursion is the natural way to work with trees, graphs, and many algorithms like DFS, dynamic programming, and backtracking. If you can’t think recursively, entire categories of problems become much harder.

The Pattern

def solve(problem):
    if problem is trivial:     # base case
        return answer
    smaller = break_down(problem)
    return combine(solve(smaller))  # recursive case

Code Examples

# Factorial: n! = n * (n-1) * ... * 1
def factorial(n: int) -> int:
    if n <= 1:          # base case
        return 1
    return n * factorial(n - 1)  # recursive case
 
assert factorial(5) == 120  # 5 * 4 * 3 * 2 * 1
 
# Fibonacci (naive — O(2^n), see DP for better)
def fib(n: int) -> int:
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
 
assert fib(10) == 55
 
# Binary search (recursive version)
def binary_search(arr: list, target: int, lo: int = 0, hi: int = None) -> int:
    if hi is None:
        hi = len(arr) - 1
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)
 
assert binary_search([1, 3, 5, 7, 9], 7) == 3

The Call Stack

Each recursive call adds a frame to the call stack. Too many calls = RecursionError (stack overflow).

factorial(4)
  → 4 * factorial(3)
    → 3 * factorial(2)
      → 2 * factorial(1)
        → returns 1         # base case hit
      → returns 2 * 1 = 2
    → returns 3 * 2 = 6
  → returns 4 * 6 = 24

Python’s default recursion limit is 1000. For deep recursion, convert to iteration or increase the limit with sys.setrecursionlimit().

Recursion vs Iteration

Recursion	Iteration
Elegant for tree/graph problems	Usually faster (no call overhead)
Uses O(n) stack space	Uses O(1) extra space
Risk of stack overflow	No stack overflow risk
Natural for divide-and-conquer	Natural for linear scans

Rule of thumb: if the problem has a recursive structure (trees, nested data), use recursion. If it’s a simple loop, use iteration.

Tail Recursion

When the recursive call is the very last operation, it’s “tail recursive.” Some languages (Scheme, Haskell) optimize this to use O(1) stack space. Python and Java do not.

Related

• Big O Notation — recursive algorithms have time and space complexity from the call stack
• Trees and Binary Search Trees — naturally recursive structures
• Dynamic Programming — recursion + memoization
• Backtracking — recursion for exploring all possibilities