Recursion

A base case that stops it, a recursive case that shrinks toward it, and a stack that remembers the rest

Base case firstand every call must move toward it
Depth is spaceone stack frame per unreturned call
Memoize repeatsthe bridge from recursion to DP
Recursion → iterationfor input with no size ceiling

1.Base case and recursive case

Every recursive function needs a base case that returns directly, with no further recursive call, and a recursive case that calls itself on a smaller version of the same problem — the base case is what stops the calls.

Key features

Every recursive call must move the input strictly closer to a base case — the same size (or a bigger) input recurses forever
A function can have more than one base case (e.g. both n == 0 and a guard for negative input)
Forgetting the base case, or writing one that is never actually reached, causes infinite recursion — Python turns that into a RecursionError, not a silent infinite loop

A base case only stops recursion if every recursive call actually moves the input closer to it — a base case that is never reached is no different from having none at all.

2.The call stack, and how recursion depth relates to space complexity

Each recursive call pushes a new frame onto the call stack, holding that call's local variables, and the frame is only popped once the call returns — so recursion depth IS the function's space complexity, not just an implementation detail.

Key features

Recursion depth (the deepest point of still-unreturned calls) is O(depth) extra space, on top of whatever space the data itself uses
Two recursive calls in the SAME function body (like naive Fibonacci) are never on the stack at the same time — the second call only starts after the first has fully returned and been popped
Python's default recursion limit exists specifically because each frame consumes real interpreter stack space — not an arbitrary round number

Recursion depth is real memory, one stack frame per unreturned call — a correct recursive function can still crash purely from depth, which is a capacity problem, not a logic bug.

3.Recursion on arrays/strings (divide the input, recurse on a piece)

A recursive function on an array or string typically peels off one element or splits the input in half, then recurses on what remains — the base case is whatever input is too small to divide any further.

Key features

'Peel off one element' recursion (reversing a string one character at a time) has depth equal to the input size — O(n) stack space
'Split in half' recursion (binary search, merge sort) has depth equal to log₂(input size) — far shallower for the same input
Slicing to build the smaller piece (nums[1:], s[mid:]) itself costs O(k) to copy — for very large inputs, passing indices instead of slices avoids that hidden copying cost

Peeling one element gives O(n) recursion depth; splitting in half gives O(log n) — check the base case covers EVERY input small enough to stop on, empty included.

4.Memoization as the bridge from recursion to dynamic programming

Memoization caches a recursive function's result for each distinct set of arguments, so a subproblem reached more than once is solved only the first time — turning an exponential-time recursion into a polynomial one.

Key features

This only helps when the SAME subproblem is reached through different call paths — a recursion where every call has unique arguments gains nothing from a cache
Naive recursive Fibonacci is O(2ⁿ) time; memoized, it becomes O(n) time at the cost of O(n) extra space for the cache
This is exactly 'top-down dynamic programming', seen again in §21 — memoization IS dynamic programming, written as recursion instead of a bottom-up table

Memoization needs BOTH halves: check the cache before recursing, and write to it before returning — storing a result without ever checking for one first buys nothing.

5.Tracing a recursion tree by hand

Drawing every recursive call as a node, connected to the calls it makes and the value it returns, turns an abstract recursive function into a picture that can actually be checked by eye.

Key features

A tree's height equals the maximum recursion DEPTH; its total node count equals the TOTAL number of calls made — two different numbers, one is space, one is total work
A node with two recursive calls (like naive Fibonacci) branches — tracing it by hand is what makes repeated, wasted subproblems visible
Values propagate back up in POST-order — a parent cannot know its own return value until every child it called has already returned one

Tracing a call tree by hand exposes exactly which subproblems get solved more than once — that repeated work is precisely what memoization exists to eliminate.

6.Head recursion vs tail recursion (Python doesn't optimize tail calls)

In tail recursion, the recursive call is the very last thing the function does. In head recursion, work happens after the recursive call returns. Python optimizes neither into a loop, so both cost the same stack space.

Key features

"Python doesn't optimize tail calls" means a tail-recursive function still uses O(depth) stack space — rewriting factorial to be tail-recursive does NOT avoid a RecursionError on large input
A tail-recursive function can always be mechanically rewritten as a plain loop, since there is no pending work to preserve across the call — this is exactly what languages with tail-call optimization automate
Head recursion genuinely needs the stack — the pending multiplication must wait for the deeper call to return before it can run

A tail call is one with nothing left to do after it returns — but in CPython that fact changes nothing about stack usage; both styles cost one frame per call.

7.Converting recursion to iteration

Any recursive function can be rewritten as a loop with an explicit stack — trading the call stack's automatic bookkeeping for a manual one that never hits Python's recursion limit.

Key features

The manual stack has to replace EVERY piece of state a stack frame would have held — not just the input, but also "what to do once the answer comes back"
A tail-recursive function converts to iteration trivially (just reassign the loop variables); a head-recursive one usually needs an explicit stack to replay its "work after the call" step in the right order
Reach for this conversion when input size could realistically exceed sys.getrecursionlimit() — not as an automatic rewrite of every recursive function

The explicit stack in an iterative rewrite replaces the call stack entirely — it has to hold everything a stack frame would have, not just the input.

8.Mutual recursion

Mutual recursion is two or more functions that call each other instead of calling themselves — A calls B, B calls A — with the base case reached by whichever function actually gets there.

Key features

Depth counts every frame from BOTH functions combined — two mutually recursive functions 50 calls deep together is still depth 50, subject to the same recursion limit as any other recursion
The classic teaching example is checking even/odd by mutual recursion — real code almost always uses n % 2 == 0 instead, but it shows the shape cleanly
A small state machine, where each state's handler calls directly into the next state's handler, is a realistic use of the same pattern

Mutual recursion is one continuous call chain split across two function bodies — it still needs exactly one thing ordinary recursion needs: a base case the alternation eventually reaches.

9.`functools.lru_cache` for automatic memoization

@functools.lru_cache wraps a function so Python automatically caches its return value per distinct set of arguments — the same speedup as a hand-written memoization dict, with one decorator line.

Key features

Every argument must be hashable, since the cache is keyed like a dict — a list argument raises TypeError immediately, a tuple works fine
maxsize=None makes the cache unbounded, matching a hand-written dict exactly; a finite maxsize evicts the least-recently-used entries once full
.cache_info() reports hits/misses/size — a way to actually confirm memoization is working, rather than assuming it from speed alone

@lru_cache(maxsize=None) is a hand-written memoization dict in one line — confirm it actually helped with .cache_info(), not just by assuming from speed.

Spotted a mistake on this page? Tell us.

Read Sheet