Recursion Cheat Sheet
Explains recursive function structure, base and recursive cases, the call stack, memoization, and recursion versus iteration tradeoffs.
Anatomy of a Recursive Function
Every recursive function needs a base case and a recursive case.
def factorial(n): if n <= 1: # base case: stops the recursion return 1 return n * factorial(n - 1) # recursive casefactorial(5) # => 120
Fibonacci & Tree Traversal
Naive vs memoized recursion, and recursive tree traversal.
# Naive recursive Fibonacci: O(2^n)def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)# Memoized Fibonacci: O(n)def fib_memo(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo) return memo[n]# Recursive in-order binary tree traversaldef inorder(node, result=None): if result is None: result = [] if node is None: return result inorder(node.left, result) result.append(node.value) inorder(node.right, result) return result
Key Concepts
Core vocabulary for reasoning about recursive functions.
- Base case- The condition that stops recursion; every recursive function must have at least one to avoid infinite recursion
- Recursive case- The part of the function that calls itself with a smaller or simpler input, progressing toward the base case
- Call stack- Each recursive call pushes a new stack frame; deep recursion can exhaust it and cause a stack overflow
- Tail recursion- A recursive call that is the last operation in the function; some languages optimize it into a loop (Python does not)
- Memoization- Caching results of expensive recursive calls by argument to avoid redundant recomputation
- Divide and conquer- A recursion pattern that splits a problem into subproblems, solves them recursively, and combines results, e.g. merge sort
Recursion vs Iteration
The same logic expressed both ways.
# Recursive sumdef sum_recursive(arr): if not arr: return 0 return arr[0] + sum_recursive(arr[1:])# Iterative equivalent (no call-stack growth)def sum_iterative(arr): total = 0 for x in arr: total += x return total
Backtracking Template
A generic recursive backtracking skeleton for generating permutations, subsets, and constraint-satisfaction solutions.
def backtrack(path, choices, results): if is_complete(path): results.append(path[:]) # copy, since path is mutated in place return for choice in choices: if not is_valid(path, choice): continue path.append(choice) # make choice backtrack(path, remaining(choices, choice), results) path.pop() # undo choice (the "backtrack" step)# Example: generate all permutations of [1, 2, 3]def permutations(nums): results = [] backtrack([], nums, results) return results
Mutual Recursion
Two functions that call each other, useful for state-machine-like parsing and even/odd style checks.
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)is_even(10) # => True, alternates between the two functions
Trampolining to Avoid Stack Overflow
Simulates tail-call optimization in languages (like Python) that lack it, by returning thunks instead of recursing directly.
def trampoline(fn, *args): result = fn(*args) while callable(result): result = result() return resultdef factorial_tramp(n, acc=1): if n <= 1: return acc return lambda: factorial_tramp(n - 1, acc * n) # return a thunk, not a calltrampoline(factorial_tramp, 10000) # runs in constant stack space
Generator-Based Traversal for Deep Trees
Uses an explicit stack with a generator to walk arbitrarily deep trees without hitting Python's recursion limit.
def iterative_deepen(node): stack = [node] while stack: current = stack.pop() if current is None: continue yield current.value stack.append(current.right) stack.append(current.left)# equivalent to a recursive pre-order traversal but with O(1) call-stack usage;# depth is bounded only by available heap memory, not sys.getrecursionlimit()
Analyzing Recursive Complexity
Tools for reasoning about the time and space cost of recursive algorithms.
- Recurrence relation- An equation expressing a recursive function's runtime in terms of itself on smaller inputs, e.g. T(n) = 2T(n/2) + O(n) for merge sort
- Master theorem- Closed-form solution for recurrences of the form T(n) = aT(n/b) + O(n^d); compares log_b(a) to d to classify the growth rate
- Recursion tree- Diagram of recursive calls as a tree where each level's total work is summed to derive overall complexity
- Space complexity of recursion- Bounded by maximum call-stack depth, not total number of calls; tail-recursive-looking code in Python still costs O(depth) frames
- Exponential blowup- Occurs when a recursive function branches into multiple recursive calls without memoization, e.g. naive Fibonacci's O(2^n)
- Continuation-passing style (CPS)- Rewriting a recursive function so the "next step" is passed explicitly as a callback, enabling tail-call-style execution in languages that optimize it
Continuation-Passing Style
Restructures recursion so every call is in tail position by threading a continuation function through the calls.
def factorial_cps(n, cont=lambda result: result): if n <= 1: return cont(1) return factorial_cps(n - 1, lambda result: cont(n * result))factorial_cps(5) # => 120, built up through the continuation chain# Note: Python still grows the call stack here since it has no TCO;# CPS is more valuable as a mental model and in languages that do optimize tail calls
Python has no tail-call optimization and a default recursion limit (around 1000 frames) — convert deep or hot-path recursion to an explicit loop rather than relying on sys.setrecursionlimit().
