A function that calls itself, and a strategy for exploring every possibility by trying, failing, and undoing. Two ideas that unlock an enormous class of problems.
π‘ IntermediateRecursion is when a function calls itself to solve a smaller version of the same problem. That's the entire idea. Everything else β base cases, the call stack, memoization β is just managing that one idea.
Recursion has roots in mathematics going back centuries. The Fibonacci sequence was described by Leonardo of Pisa (Fibonacci) in 1202, though he defined it iteratively. The idea of functions defined in terms of themselves became formalized in the 1930s through the work of Kurt GΓΆdel, Alonzo Church, and Alan Turing. Church's lambda calculus (1936) and Turing's machines both support recursive definitions β recursion turned out to be fundamental to what "computation" even means.
In programming, LISP (1958) was the first widely-used language to support recursive function calls. Before that, many languages didn't even have a call stack β they couldn't support recursion at all. Today every major language supports it, though some (like early FORTRAN and COBOL) originally didn't.
When you call a function recursively, the computer pushes a new stack frame onto the call stack (a region of memory that tracks active function calls). That frame holds the function's local variables, its parameters, and its return address (where to continue executing after the function returns). When the function returns, the frame pops off and execution resumes at the return address.
If you recurse too deeply (say, 10,000 calls deep in Python, or a few thousand in Java), you run out of stack space and get a stack overflow β the call stack has hit its size limit. Python's default recursion limit is 1,000 frames (you can increase it with sys.setrecursionlimit(), but don't go crazy β the OS stack has hard limits too).
Every recursive solution has two parts:
Backtracking is recursion with a specific strategy: explore a possibility, and if it leads to a dead end, undo it and try the next option. The three steps repeat at every decision point: make a choice, recurse, undo the choice.
Think of it like navigating a maze. At each fork, you pick a direction. If you hit a dead end, you walk back to the last fork and try a different direction. You're systematically exploring every path without getting lost because you always undo your steps.
Backtracking solves constraint satisfaction problems β problems where you need to find an arrangement that satisfies multiple rules. N-Queens (place queens so none attack each other), Sudoku (fill a grid so every row, column, and box has 1-9), and graph coloring (color nodes so no adjacent nodes share a color) are all constraint satisfaction problems.
Pruning β skipping branches you know can't lead to valid solutions β is what makes backtracking practical. Without pruning, you'd explore the entire search tree (often exponentially large). With good pruning, you can eliminate vast swaths of the tree and make what looks like an intractable problem run in seconds.
When you call factorial(4), here's what actually happens in memory:
factorial(4) calls factorial(3) β pushes a frame onto the stackfactorial(3) calls factorial(2) β another framefactorial(2) calls factorial(1) β another framefactorial(1) hits the base case, returns 1 β frame popsfactorial(2) gets 1 back, returns 2Γ1=2 β frame popsfactorial(3) gets 2 back, returns 3Γ2=6 β frame popsfactorial(4) gets 6 back, returns 4Γ6=24 β frame popsThe stack grew 4 frames deep, then unwound. That's O(n) space just for the stack, even though the "work" at each level is O(1). Every recursive algorithm has this implicit space cost.
Tail recursion is when the recursive call is the very last thing the function does β there's no work left after the call returns. In that case, the current stack frame is unnecessary (it has nothing left to do), so a smart compiler can reuse it. This converts the recursion into a loop internally, using O(1) stack space.
Unfortunately, Python and Java do not optimize tail recursion. Scheme, Haskell, and some C compilers do. In Python, you'll want to convert deep tail-recursive functions to iterative ones manually if stack depth is a concern.
Naive fib(n) calls fib(n-1) and fib(n-2). Each of those makes two calls, and so on. The result is a binary tree of calls with O(2βΏ) nodes. fib(40) makes over a billion calls. fib(50) would take minutes.
The problem: overlapping subproblems. fib(5) computes fib(3) twice, fib(2) three times, fib(1) five times. Massive redundancy.
The fix: memoization (not memorization β it comes from "memo," as in a note to yourself). Cache each result so you never compute the same subproblem twice. With memoization, fib(n) runs in O(n) time and O(n) space. This is the bridge between recursion and dynamic programming β memoized recursion IS top-down DP.
Place N queens on an NΓN chessboard so no two queens threaten each other. Queens attack along rows, columns, and diagonals.
|row1 - row2| == |col1 - col2|.The "undo" step β removing the queen β is what makes it backtracking rather than plain recursion. You're exploring a decision tree: each node is a partially-filled board, each branch is a column choice, and leaves are either complete solutions or dead ends.
Pruning in action: Without pruning, you'd try all N^N possible placements (every column in every row). With the constraint checks, you prune branches as soon as a conflict is detected. For N=8, the full tree has 8^8 = 16.7 million leaves, but pruning reduces the search to about 15,000 nodes. That's a 1000x reduction.
Switch between two visualizations: a Fibonacci recursion tree (watch redundant calls pile up) and an N-Queens backtracking solver.
f(n) with f(n) or f(n+1), you'll loop forever. Common trap: in backtracking, forgetting to advance the index or position, so you keep trying the same element over and over.
modify β recurse β un-modify.
sys.setrecursionlimit() or convert to an iterative approach with an explicit stack. In interviews, mention this trade-off even if you write the recursive solution.
Recursive complexity depends on two things: the branching factor (how many recursive calls per level) and the depth (how deep the recursion goes). The number of nodes in the recursion tree is roughly branchingFactordepth.
For space complexity, remember that each active frame uses memory. The maximum number of simultaneous frames is the depth of the deepest branch β that's your stack space. Memoization adds additional space for the cache.
| Algorithm | Time | Space | Notes |
|---|---|---|---|
| Factorial | O(n) | O(n) | Linear recursion, n stack frames |
| Fibonacci (naive) | O(2βΏ) | O(n) | Exponential time, tree depth = n |
| Fibonacci (memo) | O(n) | O(n) | Each subproblem computed once |
| Binary search (recursive) | O(log n) | O(log n) | Stack depth = log n |
| Merge sort | O(n log n) | O(n) | Divides in half, merges linearly |
| Permutations | O(n Γ n!) | O(n) | n! leaves, O(n) work per leaf |
| N-Queens | O(n!) | O(n) | Pruning helps enormously in practice |
| Subsets/power set | O(n Γ 2βΏ) | O(n) | 2βΏ subsets, O(n) to copy each |
from functools import lru_cache
@lru_cache(maxsize=None) # Python's built-in memoization decorator
def fib(n):
"""Fibonacci with automatic caching. First call computes;
subsequent calls with same n return cached result in O(1)."""
if n <= 1:
return n
# Trust that fib(n-1) and fib(n-2) return correct answers
return fib(n - 1) + fib(n - 2)
# Manual memoization β same idea, explicit cache
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]
# Iterative conversion β O(1) space, no stack risk
def fib_iterative(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
function fib(n, memo = {}) {
if (n in memo) return memo[n];
if (n <= 1) return n;
// Cache the result before returning
memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
return memo[n];
}
def solve_n_queens(n):
"""Find all valid placements of n queens on an nΓn board.
Uses sets for O(1) conflict checking on columns and diagonals."""
solutions = []
board = [-1] * n # board[row] = column where queen is placed
# Track occupied columns and diagonals for O(1) lookup
cols = set() # Occupied columns
diag1 = set() # Occupied "\" diagonals (row - col is constant)
diag2 = set() # Occupied "/" diagonals (row + col is constant)
def backtrack(row):
if row == n:
# All queens placed β record this solution
solutions.append(board[:])
return
for col in range(n):
# Check all three constraints in O(1)
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue # Pruning: skip invalid placements
# Make the choice
board[row] = col
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
backtrack(row + 1) # Recurse to next row
# Undo the choice (backtrack)
board[row] = -1
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return solutions
def subsets(nums):
"""Generate all 2^n subsets. At each element, two choices:
include it or skip it. This creates a binary decision tree."""
result = []
def backtrack(index, current):
if index == len(nums):
result.append(current[:]) # Reached a leaf β record subset
return
# Choice 1: skip this element
backtrack(index + 1, current)
# Choice 2: include this element
current.append(nums[index])
backtrack(index + 1, current)
current.pop() # Undo (backtrack)
backtrack(0, [])
return result
# Alternative: iterative bit manipulation
def subsets_bits(nums):
"""Each integer from 0 to 2^n - 1 represents a subset.
Bit i is 1 β include nums[i]. Bit i is 0 β exclude."""
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = [nums[i] for i in range(n) if mask & (1 << i)]
result.append(subset)
return result
def permutations(nums):
"""Generate all n! orderings. At each position, try every
remaining element. Backtrack by removing the choice."""
result = []
def backtrack(path, remaining):
if not remaining:
result.append(path[:]) # Complete permutation
return
for i in range(len(remaining)):
path.append(remaining[i]) # Choose
# Explore: recurse without element i
backtrack(path, remaining[:i] + remaining[i+1:])
path.pop() # Un-choose
backtrack([], nums)
return result
File systems are trees. Directories contain files and other directories. Listing all files under a directory is a naturally recursive operation β you process the current directory's contents, and for each subdirectory, you recursively process its contents too.
import os
def find_files(directory, extension=".py"):
"""Recursively find all files with a given extension.
This is what tools like 'find' and 'grep -r' do internally.
The directory tree IS the recursion tree:
- Base case: a file (leaf node) β check if it matches
- Recursive case: a directory β process its children"""
matches = []
for entry in os.listdir(directory):
full_path = os.path.join(directory, entry)
if os.path.isfile(full_path):
# Base case: it's a file
if full_path.endswith(extension):
matches.append(full_path)
elif os.path.isdir(full_path):
# Recursive case: it's a directory β go deeper
matches.extend(find_files(full_path, extension))
return matches
# Usage
python_files = find_files("/home/user/project", ".py")
for f in python_files:
print(f)
# This is equivalent to: find /home/user/project -name "*.py"
# The recursion depth equals the deepest directory nesting level.
# For typical projects, that's 5-15 levels β well within stack limits.
Every time you run ls -R, find, du, or tree, you're running a recursive directory traversal. The file system is one of the most natural examples of recursion in everyday computing β the data structure itself is recursive (a directory contains directories), so the algorithm to process it is recursive too.
for each choice: make it β recurse β undo it. The variations are just what "choice" means: which column for a queen, which number for a Sudoku cell, which letter for a phone number digit. Learn the template, then adapt. Write it on the whiteboard first, then fill in the problem-specific logic.
if i > start and nums[i] == nums[i-1]: continue. This avoids generating the same subset/permutation twice without needing a set for deduplication.