Recursion
A function that solves a problem by calling itself on a smaller piece. It needs a base case and progress toward it.
Level: intermediate
What is it?
Recursion solves a problem by reducing it to a smaller instance of itself. Every recursive function has a base case that answers directly and a recursive case that calls itself on a smaller input. Each pending call keeps a frame on the call stack, so recursion depth is limited by stack size.
Why does it matter?
Trees, graphs, parsing, divide and conquer, and backtracking are naturally recursive. Once you can see the smaller problem inside the larger one, code that needs a page of loops and manual stacks fits in a few lines.
Mental model
Russian nesting dolls. To count the dolls, open one, count 1, then ask the same question of the doll inside. The smallest doll — the one with nothing in it — is the base case.
How it works
- Two parts: a base case that stops, and a recursive case that moves strictly toward it.
- The call stack holds one frame per unfinished call. Python's default limit is about 1,000 frames; deep recursion raises RecursionError.
- Overlapping subproblems make naive recursion explode (Fibonacci is O(2ⁿ)). Memoization caches results and makes it O(n).
- Any recursion can be rewritten with a loop and an explicit stack. Choose recursion when it matches the shape of the data.
- Tail recursion can reuse a frame in languages that optimize it; Python and Java do not.
Steps
- Ask: is it small enough to answer now?
- If so, return the base value
- Otherwise shrink the problem
- Call yourself on the smaller piece
- Combine the answer and return
Code example: Base case, smaller calls, memoization
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2: # base cases
return n
return fib(n - 1) + fib(n - 2) # smaller subproblems
print(fib(50)) # 12586269025Complexity and trade-offs
Time: Naive Fibonacci O(2ⁿ); with memoization O(n)
Space: O(depth) for the call stack
Trade-offs
- Short, direct code for recursive data such as trees
- Stack depth is a hard limit; a loop with an explicit stack has none
- Memoization trades memory for a large drop in time
Real-world usage
- Walking trees and directories
- Divide and conquer: merge sort, quicksort, binary search
- Backtracking: solvers, parsers, combinatorial search
Common mistakes
- Forgetting the base case, or writing one the input can never reach.
- Recomputing the same subproblem exponentially many times.
- Recursing a million deep on a list where a loop would do.
Interview questions
What are the two parts of every recursive function?
A base case that returns without recursing, and a recursive case that calls the function on a strictly smaller input so it must eventually reach the base case.
Why can recursion overflow the stack, and how do you avoid it?
Each pending call holds a stack frame, and the stack is finite. Convert to a loop with an explicit stack, reduce the depth (divide and conquer halves it each time), or use an iterative algorithm.
How does memoization change Fibonacci's cost?
The naive version recomputes the same values and takes O(2ⁿ) time. Caching each fib(k) after the first computation means each is computed once, so time is O(n).