Python Recursion and Iterative Conversion

Recursion is a way of expressing “solve this in terms of a smaller version of itself.” It’s elegant on paper, but in Python it costs real stack frames (the previous lesson) and, done naively, can recompute the same work over and over. This lesson closes Phase 1 by making recursion concrete: how to write it correctly, when it’s wasteful, and how to convert it to iteration.

What you’ll learn

Base case vs recursive case — the two parts every recursive function needs.
Why naive recursive Fibonacci does exponential work.
Converting recursion to iteration with an explicit stack.
Instant memoization with functools.lru_cache.
Why Python has no tail-call optimization, and what that means for you.

Base case and recursive case

Every correct recursive function needs exactly two parts: a base case that stops the recursion, and a recursive case that makes progress toward it.

base_recursive_case.py

def factorial(n):
    if n <= 1:                  # base case: stops the recursion
        return 1
    return n * factorial(n - 1) # recursive case: smaller subproblem
 
print(factorial(6))

Miss the base case (or never actually shrink toward it) and you get infinite recursion — which in Python surfaces as a RecursionError once the stack limit from the previous lesson is hit.

The cost of naive recursion: Fibonacci

$fib(n) = fib(n-1) + fib(n-2)$ looks harmless, but each call branches into two more calls, and many of those calls compute the exact same subproblem repeatedly.

diagram Recursion tree for naive fib(5) — note the repeated subtrees mermaid

  graph TD
    A["fib(5)"] --> B["fib(4)"]
    A --> C["fib(3)"]
    B --> D["fib(3)"]
    B --> E["fib(2)"]
    D --> F["fib(2)"]
    D --> G["fib(1)"]
    C --> H["fib(2)"]
    C --> I["fib(1)"]

fib(3) shows up twice, fib(2) shows up three times — and that duplication compounds as n grows, giving naive Fibonacci $O(2^n)$ time.

naive_fib.py

call_count = 0
 
def fib(n):
    global call_count
    call_count += 1
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)
 
print("fib(20) =", fib(20))
print("calls made:", call_count)   # grows exponentially with n

Visual intuition

The call tree for naive Fibonacci, and the same function once it remembers what it has already computed. The second tree is the whole argument for memoisation:

recursionfib(6) without a cache: the same subtrees, over and overO(φ^n) calls

call stack

1def fib(n):2    if n <= 1:3        return n4    return fib(n - 1) + fib(n - 2)

n6calls so far1

callfib(6) needs fib(5) and fib(4). Neither is known, so both are computed from scratch — including everything they in turn need.

1/51

Count how many times fib(3) appears as a fully-expanded subtree. Every repeat returns an identical answer, and that redundancy is what grows exponentially -- 25 calls here for a function with 7 distinct inputs.

recursionWith a cache: each distinct input is computed exactly onceO(n) calls

call stack

f10

1from functools import cache2 3@cache                      # the entire fix4def fib(n):5    if n <= 1:6        return n7    return fib(n - 1) + fib(n - 2)

n10cached0calls1

callfib(10) is not cached yet, so it recurses — but only this once. Every later request for fib(10) will be a hit.

1/39

Cache hits terminate immediately instead of expanding. n = 10 fits comfortably here while the naive tree above had to be capped at 6 -- which is itself the demonstration.

Converting recursion to iteration with an explicit stack

Any recursive function can be rewritten iteratively by managing your own stack (a plain list) instead of relying on Python’s call stack — useful both for speed and to sidestep the recursion limit entirely.

iterative_factorial.py

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)
 
def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):     # a simple loop replaces the call stack
        result *= i
    return result
 
def factorial_explicit_stack(n):
    stack = []
    while n > 1:
        stack.append(n)           # push, mimicking a recursive call
        n -= 1
    result = 1
    while stack:
        result *= stack.pop()     # pop, mimicking the return + multiply
    return result
 
print(factorial_recursive(6), factorial_iterative(6), factorial_explicit_stack(6))

All three give the same answer; the last two use $O(1)$ (loop) or $O(n)$ (explicit stack list, but no Python call stack) auxiliary space instead of $O(n)$ Python stack frames.

Memoization with functools.lru_cache

Recursion’s repeated-work problem often has a one-line fix: cache each input’s result the first time it’s computed, and reuse it instead of recomputing.

memo_fib.py

from functools import lru_cache
import time
 
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
 
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
 
n = 28
 
start = time.perf_counter()
naive_result = fib_naive(n)
naive_time = time.perf_counter() - start
 
start = time.perf_counter()
memo_result = fib_memo(n)
memo_time = time.perf_counter() - start
 
print(f"naive fib({n}) = {naive_result}, took {naive_time:.4f}s")
print(f"memo  fib({n}) = {memo_result}, took {memo_time:.6f}s")
print("memoization cuts fib from exponential-time to O(n) — same recursive code, one decorator")

No tail-call optimization

Some languages (Scheme, Haskell, and others) detect when a recursive call is the very last thing a function does and rewrite it into a loop internally, using constant stack space no matter how deep the recursion goes.

CPython deliberately does not do this. Every recursive call — tail position or not — adds a real stack frame, counted against the recursion limit from the previous lesson.

Dry run

Naive Fibonacci: the call count, measured

`n`	`fib(n)`	Calls made	$2^n$	$\phi^n$	calls / $\phi^n$
10	55	177	1,024	123	1.44
20	6,765	21,891	1,048,576	15,121	1.45
25	75,025	242,785	33,554,432	167,673	1.45
30	832,040	2,692,537	1,073,741,824	1,859,326	1.45

The ratio against $\phi^n$ is a constant 1.45 at every size — which is what $\Theta(\phi^n)$ means. The ratio against $2^n$ is not constant: $2^{30}$ overestimates the real call count by about 400x.

So naive Fibonacci is $\Theta(\phi^n)$ , not $\Theta(2^n)$ , where $\phi \approx 1.618$ . The recurrence is the Fibonacci recurrence — $T(n) = T(n-1) + T(n-2) + O(1)$ — so the number of calls grows at the Fibonacci rate by definition. $2^n$ is a correct upper bound and a wrong tight bound, and quoting it as tight is the standard imprecision here.

Why so many calls for so little work? fib(30) is 832,040 and takes 2.7 million calls, because the tree recomputes the same subproblems over and over — fib(28) is evaluated twice, fib(27) three times, fib(26) five times, and so on down. Those multiplicities are themselves Fibonacci numbers.

Memoisation, measured

Version	`fib(25)`
Naive recursion	25.15 ms
`@lru_cache`	0.0159 ms

A ~1,600x speedup from one decorator. The call count drops from 242,785 to 26 — one per distinct n from 0 to 25 — because each subproblem is computed once and read thereafter. That is the whole of dynamic programming in one line: the recursion was already correct, and it was only ever slow because it forgot.

Note the cache makes the time linear but the stack depth is unchanged at $O(n)$ — the first descent still goes all the way down before anything returns. So @lru_cache fixes the recomputation and not the recursion limit; fib(5000) still raises RecursionError with the decorator attached.

Recursion to an explicit stack

The mechanical conversion, on a tree in-order walk:

Recursive	Explicit stack
implicit call frames	a `list` used as a stack
“descend left, then visit, then descend right”	push the left spine, pop-and-visit, push the popped node’s right spine
depth limited to ~1,000	limited only by heap memory
$O(h)$ frames	$O(h)$ heap — same order, no frame limit

The conversion does not reduce the space complexity — it moves the storage from the C stack to the heap, where there is no ~1,000-entry ceiling. That distinction is worth stating precisely: an iterative rewrite fixes the RecursionError, not the $O(h)$ .

For a tail recursion — where the recursive call is the last thing that happens — the conversion is even simpler: rebind the arguments and loop, using $O(1)$ space. Python has no tail-call optimisation, so it will not do this for you no matter how the function is written.

Practice

Drill 1 — the base case. Complete a recursive sum over a list; the base case is the empty list.

Drill 2 — convert to iteration. Rewrite the same sum with a plain loop instead of recursive calls.

Drill 3 — memoize it. Add the missing import so lru_cache can decorate a recursive Fibonacci.

Complexity

Shape	Time	Space	Note
Linear recursion, `T(n) = T(n-1) + O(1)`	$O(n)$	$O(n)$ frames	dies at ~1,000 in CPython
Tail recursion	$O(n)$	$O(n)$ frames in Python — no TCO	rewrite as a loop for $O(1)$
Binary recursion, `T(n) = 2T(n/2) + O(1)`	$O(n)$	$O(\log n)$ balanced, $O(n)$ degenerate	tree traversal
Naive Fibonacci, `T(n) = T(n-1) + T(n-2)`	$\Theta(\phi^n)$	$O(n)$	not $2^n$ — measured 1.45 $\phi^n$
Memoised Fibonacci	$O(n)$	$O(n)$ cache + $O(n)$ frames	the depth is unchanged
Bottom-up iterative Fibonacci	$O(n)$	$O(1)$ with two variables	no stack at all
Subsets / power set	$O(2^n \cdot n)$	$O(n)$ depth	the output is the cost
Permutations	$O(n! \cdot n)$	$O(n)$ depth	—

Three things to be precise about:

Memoisation fixes time, not depth. @lru_cache turns $\Theta(\phi^n)$ into $O(n)$ but leaves $O(n)$ frames, so it does not save you from RecursionError. Bottom-up iteration fixes both.
@lru_cache is $O(\text{distinct arguments})$ space, and it holds references to them until cleared. maxsize=None means unbounded; on a long-running process that is a leak.
The cache key is the argument tuple. So the arguments must be hashable — no lists or dicts — and a function whose behaviour depends on anything outside its arguments will be cached wrongly. Converting a list argument to a tuple is the usual workaround.

Pitfalls

A base case that is never reached. n <= 0 versus n == 0 matters the moment a caller passes a negative number: n == 0 recurses forever. Guard the range, not the single value.
Recursing before the base case check. The check must come first, or the recursion goes one level too deep — often harmless, sometimes an IndexError on arr[n].
Quoting naive Fibonacci as $O(2^n)$ . Measured: 2,692,537 calls at $n = 30$ against $2^{30} \approx 1.07$ billion. It is $\Theta(\phi^n)$ ; $2^n$ is a loose upper bound.
Expecting @lru_cache to fix the recursion limit. It fixes recomputation. The first descent still builds $O(n)$ frames, so fib(5000) raises with or without it.
Unhashable arguments to @lru_cache. A list argument raises TypeError; convert to a tuple. And a function reading mutable global state will serve stale cached answers, because that state is not part of the key.
A cache that outlives its validity. If the function’s meaning depends on data captured from the enclosing scope — a digit list, a grid — the cache must be cleared when that data changes. cache_clear() exists for exactly this.
Expecting tail-call optimisation. Python has none, deliberately — Guido has said tracebacks are worth more. A tail-recursive function is not cheaper than any other recursion in CPython.
Converting to an iterative version and claiming $O(1)$ space. An explicit stack is still $O(h)$ ; it just lives on the heap where there is no frame ceiling. Only tail recursion converts to $O(1)$ .
Mutable default arguments in a recursive helper. def go(path=[]) shares one list across every top-level call. Use None and create it inside.
Returning nothing from the recursive branch. if cond: go(...) without return silently gives None on that path — the single most common recursion bug in Python, because it fails as a TypeError far from the cause.

Interview follow-ups

They ask	What they’re checking	The answer
“What is naive Fibonacci’s complexity?”	Precision	$\Theta(\phi^n)$ , $\phi \approx 1.618$ . Measured call counts are a constant 1.45 $\phi^n$ at $n = 10, 20, 25, 30$ ; $2^n$ overshoots 400x at $n = 30$ and is only an upper bound
“Make it fast”	The cheapest fix first	`@lru_cache` — one decorator, $\Theta(\phi^n)$ to $O(n)$ , measured ~1,600x on `fib(25)`. Then note it does not fix the stack depth
“Make it $O(1)$ space”	Whether you see the bottom-up form	Two variables in a loop, no recursion. Memoised top-down is $O(n)$ cache plus $O(n)$ frames; bottom-up is genuinely constant
“Convert this recursion to iteration”	The mechanical process	Replace the implicit frames with an explicit stack holding what each frame held. For a tree in-order walk: push the left spine, pop-and-visit, push the popped node’s right spine
“Does that reduce the space?”	Whether you overclaim	No — $O(h)$ either way. It moves the storage from the C stack to the heap, so the ~1,000-frame limit no longer applies. That fixes `RecursionError`, not the order
“Does Python optimise tail calls?”	A common misconception	No, deliberately — the design choice favours full tracebacks. So a tail-recursive function costs the same frames as any other, and you convert it by hand: rebind the arguments and loop, $O(1)$
“The input is 10,000 elements deep”	Practical limits	Iterative, or `setrecursionlimit` plus a thread with a larger stack. Measured: the default limit is 1,000 and you actually reach 998, because every frame in the chain counts
“What does `@lru_cache` use as the key?”	The gotchas	The argument tuple — so arguments must be hashable, and anything the function depends on outside its arguments is invisible to the cache and will serve stale results. `cache_clear()` when that state changes
“When is recursion the right choice?”	Judgement	When the problem is defined recursively and the depth is bounded by $\log n$ — trees, divide and conquer, backtracking. For linear recursion over a list or a large range, a loop is both faster and safe

Self-check

pch.quizTag pch.quizDefaultTitle

Naive recursive Fibonacci makes 2,692,537 calls at n = 30. What is its tight bound?

pch.quizShowAnswer

B — Theta(phi^n) with phi = 1.618 -- measured call counts are a constant 1.45 phi^n at every n, while 2^30 overshoots by about 400x — The recurrence T(n) = T(n-1) + T(n-2) + O(1) is the Fibonacci recurrence, so the call count grows at the Fibonacci rate. Dividing measured calls by phi^n gives 1.44, 1.45, 1.45, 1.45 at n = 10, 20, 25, 30 -- a constant, which is what a tight bound looks like. 2^n is correct as an upper bound and wrong as a tight one.
Adding @lru_cache to fib takes fib(25) from 25.15 ms to 0.0159 ms. Does it also fix the recursion limit?

pch.quizShowAnswer

B — No -- the first descent still builds O(n) frames, so fib(5000) raises RecursionError with or without the decorator — The cache eliminates *repeated* subproblems, not the initial descent: fib(25) still calls fib(24) which calls fib(23) all the way to the base case before anything returns. Calls drop from 242,785 to 26, but depth stays at 25. Bottom-up iteration is what fixes both -- two variables, O(1) space, no frames.
You convert a recursive tree traversal to use an explicit stack. What does that buy?

pch.quizShowAnswer

B — The space stays O(h) but moves to the heap, where the ~1,000-frame limit does not apply -- so it fixes RecursionError, not the order — Overclaiming here is common. The explicit stack holds exactly what the call frames held, so the order is unchanged; what changes is *where* it lives. Heap allocation has no equivalent of the interpreter's frame ceiling, which is why iterative versions survive a 10,000-node degenerate tree and recursive ones do not.
Does Python optimise tail calls?

pch.quizShowAnswer

B — No, deliberately -- the design favours complete tracebacks, so a tail-recursive function costs the same frames as any other — It is an explicit language design decision rather than an oversight, and the reasoning is that eliminating frames destroys the traceback. The practical consequence is that writing a recursion in tail position buys nothing in CPython -- you convert it yourself by rebinding the arguments and looping, which gives genuine O(1) space.
What does @lru_cache use as its cache key, and why does that matter?

pch.quizShowAnswer

B — The argument tuple -- so arguments must be hashable, and anything the function depends on OUTSIDE its arguments is invisible to the cache — Two consequences. A list argument raises TypeError -- convert to a tuple. And a function that reads a captured variable (a digit list, a grid) will serve results computed for the *previous* value of it, with no error at all. That is why cache_clear() exists, and why the digit-DP page insists on calling it.
Which recursion bug fails furthest from its cause in Python?

pch.quizShowAnswer

B — A missing `return` on the recursive branch -- the function silently yields None, and the TypeError surfaces somewhere else entirely — `if cond: go(...)` without `return` computes the right answer and discards it. Nothing raises at the recursion site; the None propagates and blows up wherever the caller tries to use it arithmetically. A missing base case at least fails loudly and at the right place.
When is recursion genuinely the right choice in Python?

pch.quizShowAnswer

B — When the structure is recursive AND the depth is bounded by about log n -- trees, divide and conquer, backtracking — Both halves matter. Recursion on a balanced tree is log n deep and reads far better than the stack version. Linear recursion over a list or a range is the same depth as the input, which in CPython means a hard ceiling at about a thousand -- and there a loop is both faster and safe. Backtracking sits in the first camp because its depth is the solution length, not the input size.

Recall card

Every recursion needs a base case that is reachable — guard the range (n <= 0), not one value.
Naive Fibonacci is $\Theta(\phi^n)$ , $\phi \approx 1.618$ — measured 1.45 $\phi^n$ at every n. $2^n$ overestimates 400x at n = 30.
@lru_cache fixes recomputation, not depth: fib(25) 25.15 ms -> 0.0159 ms (~1,600x), calls 242,785 -> 26, but still $O(n)$ frames. fib(5000) still raises.
Bottom-up iteration fixes both — two variables, $O(1)$ space.
The cache key is the argument tuple. Arguments must be hashable; anything captured from outside is invisible to the key, so cache_clear() when it changes.
Converting to an explicit stack keeps $O(h)$ — it moves storage to the heap, removing the ~1,000-frame ceiling. It fixes RecursionError, not the order.
Only tail recursion converts to $O(1)$ , and Python has no TCO — deliberately, to preserve tracebacks. Rewrite by hand.
The return-less recursive branch is the nastiest bug — silent None, failing far from the cause.
No mutable default arguments in recursive helpers (path=[] is shared).
Recursion is right when the structure is recursive and the depth is $O(\log n)$ . Linear recursion over a list should be a loop.

Recap

Every recursive function needs a base case (stops it) and a recursive case (progresses toward it).
Naive recursive Fibonacci is $O(2^n)$ because it recomputes identical subproblems many times over.
Any recursion can be rewritten iteratively with an explicit stack, or sped up instantly with functools.lru_cache.
CPython has no tail-call optimization — recursion depth always costs real stack frames, no matter how it’s written.

Next: Phase 2 — Python for DSA & CP, starting with how Python’s built-in containers actually store data and why that decides Accepted vs TLE.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading