A function that calls itself is not magic — it is stack frames piling up and unwinding. Watch them build, watch the answers come back, and watch naive Fibonacci explode into thousands of redundant calls.
Overview
Quick Context
Recursion is a function calling itself on a smaller version of the same problem. It needs exactly two things: a base case that stops the descent, and a recursive case that moves toward it.deffactorialif1return1# base casereturnfactorial1# recursive case
Controls
n5
The Call Stack
step 0
Stack frames (newest on top)
Call trace
Insight
Every call pushes a stack frame holding its arguments, locals and return address. Returning pops it. Recursion is just this, repeated.
total calls0
max depth0
result–
Complexity
factorialO(n)
fib naiveO(2^n)
fib memoisedO(n)
Recursion and the Call Stack
Where beginners get stuck — not on the idea, but on what the machine is actually doing.
The Call Stack Does the Remembering
The confusing part is that a recursive function does not finish before calling itself again. factorial(5) must pause, wait for factorial(4), and only then multiply.
Each paused call keeps its own frame — its own copy of n and its own place to resume. Step through and watch frames stack up on the way down, then unwind as answers travel back up. Nothing is computed until the base case is reached; everything is computed on the way back.
Stack Overflow Is Real
Select countdown — no base case. Frames pile up and never pop, because nothing stops the recursion. Memory reserved for the stack is finite, so eventually the program crashes with a stack overflow.
Typical limits are a few thousand frames (Python defaults to 1000). Every recursive function you write needs a base case that is genuinely reachable — a base case that the recursion never hits is no base case at all.
Naive Fibonacci: The Cautionary Tale
Choose fibonacci — naive and raise n. The call counter grows explosively, because fib(n) calls fib(n-1) and fib(n-2), which recompute the same values over and over. That is O(2ⁿ): fib(30) needs over 1.3 million calls to return a number you could compute by hand.
Now switch to memoised at the same n. Results are cached the first time, so each value is computed once and the call count collapses to roughly 2n — from exponential to linear, with a dictionary. That is dynamic programming in one change, and it is the subject of the next module.
When to Use It
Recursion shines on self-similar problems: trees, nested structures, divide-and-conquer, backtracking. Traversing a BST recursively is three lines; iteratively it needs an explicit stack.
Prefer a loop when the problem is linear — a recursive sum of an array just burns stack frames for nothing. And note that some languages (though not Python or JavaScript) optimise tail recursion into a loop, avoiding the stack growth entirely.
A function that calls itself
Recursion solves a problem by solving a smaller instance of the same problem. Two parts are required, and omitting either is the classic failure:
A base case that returns without recursing. A recursive case that moves towards the base case.
def factorial(n):
if n <= 1: # base case
return 1
return n * factorial(n - 1) # recursive case, strictly smaller
"Moves towards the base case" is the part that needs checking. factorial(n - 1) reduces n by one, so it must eventually reach 1. A recursive call that does not strictly reduce the problem produces infinite recursion, and Python raises RecursionError after about 1,000 frames.
What the call stack actually holds
Each call allocates a frame containing the function's local variables, its arguments, and where to return to. Frames stack up, and unwind as calls return.
Tracing factorial(4):
Stack (top last)
Action
factorial(4)
calls factorial(3)
factorial(4), factorial(3)
calls factorial(2)
factorial(4), factorial(3), factorial(2)
calls factorial(1)
… factorial(1)
returns 1
… factorial(2)
returns 2
factorial(4), factorial(3)
returns 6
factorial(4)
returns 24
Two consequences follow directly.
Recursion depth costs memory. Depth n means n frames, so recursion is O(n) space even when the equivalent loop is O(1).
The stack has a limit. Python's is around 1,000 frames by default, deliberately conservative to fail cleanly rather than segfaulting. That limit is why recursion over a large list or a long chain must be converted to iteration.
import sys
sys.setrecursionlimit(10_000) # raises the limit, up to the real C stack
Raising it works and moves the failure mode from a clean exception to a possible crash. Converting to iteration is the more robust answer.
Where recursion is the natural expression
Recursion is not a general substitute for loops. It is the right choice when the data or the problem is recursive.
Problem
Why recursion fits
Tree traversal
A tree's children are trees
Divide and conquer
Merge sort, quick sort, binary search
Backtracking
Try, recurse, undo
Nested structures
JSON, directory trees, expression parsing
Graph DFS
The recursion stack is the current path
Mathematical recurrences
Fibonacci, Catalan numbers, Ackermann
Iterating over a flat list, by contrast, is a loop — writing it recursively adds stack frames for nothing.
The graph row is worth expanding: DFS's recursion stack holds exactly the path from the root to the current node, which is why cycle detection and topological sorting fall out so naturally. Reproducing that iteratively requires maintaining the path explicitly.
What the stack is holding, and what it costs
Recursion is often explained as a function calling itself, which is the least interesting part of it. The useful mental model is the stack of paused frames, and you can print it: every frame is real, every frame costs memory, and the depth limit is a number you can go and read.
example_01.pyPython
import sys
def factorial(n, depth=0):
indent = " " * depth
print("%scall factorial(%d)" % (indent, n))
if n <= 1:
print("%sreturn 1 <- base case, the unwinding starts here" % indent)
return 1
result = n * factorial(n - 1, depth + 1)
print("%sreturn %d * factorial(%d) = %d" % (indent, n, n - 1, result))
return result
factorial(5)
# Read the indentation. Every "call" line goes deeper and nothing is
# computed on the way down -- the multiplications all happen on the way
# back up, in reverse order. Those five paused frames each hold their own
# n, waiting for the call below to return. That waiting is the whole
# reason recursion needs memory that iteration does not.
print()
print("Python's recursion limit:", sys.getrecursionlimit())
def depth_probe(n=0):
try:
return depth_probe(n + 1)
except RecursionError:
return n
print("frames this function actually reached:", depth_probe())
# That limit is a guard, not a hardware fact: Python raises RecursionError
# before the C stack overflows, because a real overflow is a segfault
# rather than an exception. A linked list of 10,000 nodes traversed
# recursively hits it; the same traversal in a while loop does not.
#
# The cautionary tale is naive fibonacci, where the same subproblems are
# recomputed on separate branches.
calls = {"n": 0}
def fib(n):
calls["n"] += 1
return n if n < 2 else fib(n - 1) + fib(n - 2)
print()
print("%4s %12s %14s" % ("n", "fib(n)", "calls made"))
for n in (10, 20, 25, 30):
calls["n"] = 0
v = fib(n)
print("%4d %12d %14d" % (n, v, calls["n"]))
# The call count grows faster than the answer does. Each n adds roughly
# 60% more calls, because the recursion tree branches twice at every level
# and the two halves never share their work.
#
# One dictionary fixes it, and the contrast is the point:
memo = {}
mcalls = {"n": 0}
def mfib(n):
mcalls["n"] += 1
if n < 2:
return n
if n not in memo:
memo[n] = mfib(n - 1) + mfib(n - 2)
return memo[n]
print()
for n in (30, 100):
memo.clear(); mcalls["n"] = 0
v = mfib(n)
print("memoised fib(%d) = %d in %d calls" % (n, v, mcalls["n"]))
# fib(30) went from over a million calls to under sixty. And fib(100) --
# which the naive version could not finish in the lifetime of this page --
# returns immediately. Same recursion, same base case; the only change is
# refusing to solve a subproblem twice.
Output
Guided experiments
Step through factorial(5). Watch five frames build downward, then multiply back up as each returns. Nothing multiplies until the base case is hit.
Note where the answer appears. All the real work happens during the unwinding, not the descent.
Run naive fibonacci at n=5, then n=10. The call count roughly quadruples for five extra steps — exponential growth, visible.
Switch to memoised at the same n. Same answer, a fraction of the calls, because repeats are served from the cache.
Select countdown with no base case. Frames accumulate without limit — a stack overflow in slow motion.
Summing up
Recursion is the call stack made visible: each call gets a frame, frames build on the way down and unwind on the way back. Always ensure the base case is reachable, and watch for repeated subproblems — memoising them is the difference between exponential and linear.
Converting recursion to iteration
Two situations, and they need different techniques.
Tail recursion — the recursive call is the last operation, with nothing left to do after it — converts to a simple loop:
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
Some languages eliminate tail calls automatically so the stack does not grow. Python deliberately does not, on the grounds that stack traces are more valuable for debugging. So tail recursion in Python still consumes frames, and the loop is genuinely better.
Non-tail recursion — work remains after the recursive call, as in tree traversal — needs an explicit stack:
def inorder_iter(root):
out, stack, node = [], [], root
while stack or node:
while node: # go left as far as possible
stack.append(node)
node = node.left
node = stack.pop()
out.append(node.value) # visit
node = node.right # then go right
return out
That is what recursion was doing implicitly. The explicit version is longer and harder to read, which is exactly why recursion is preferred where depth allows.
Memoisation: recursion made efficient
Naive recursive Fibonacci recomputes the same values enormously many times — O(2ⁿ) calls, because fib(n-1) and fib(n-2) share almost all their work.
Caching results collapses it to O(n):
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
return n if n < 2 else fib(n-1) + fib(n-2)
n
Naive calls
Memoised calls
20
21,891
21
40
331,160,281
41
One decorator, and an impossible computation becomes instant. The requirement is that arguments are hashable — tuples rather than lists.
This is dynamic programming in its top-down form, and it is the single most valuable thing to know about making recursion practical.
Common mistakes
No base case, or one that is unreachable — infinite recursion.
A recursive call that does not shrink the problem, which is the same failure in disguise.
Forgetting to return the recursive result.factorial(n-1) without return gives None.
Mutable default arguments as accumulators — def f(n, acc=[]) shares one list across all calls.
Exceeding the recursion limit on deep input; convert to iteration.
Recomputing subproblems without memoisation, turning a linear problem exponential.
Recursing over a flat structure where a loop is clearer and cheaper.
Questions people ask
Is recursion slower than iteration? In Python, yes — each call has function-call overhead and a frame. Prefer it for clarity on recursive structures, not for speed.
Why does Python limit recursion depth? To raise a clean RecursionError rather than overflowing the C stack and crashing.
Does Python optimise tail calls? No, deliberately — the maintainers prioritise usable stack traces.
How deep can I recurse? About 1,000 frames by default; raising the limit works up to the actual stack size.
When should I choose recursion? When the data is recursive — trees, nested structures, divide and conquer, backtracking.
What is mutual recursion? Two functions calling each other, which is common in recursive-descent parsers.
Recap in one screen
A base case and a strictly smaller recursive case are both required.
Each call holds a stack frame, so depth n costs O(n) memory and Python caps it around 1,000.
Tail recursion converts to a loop; non-tail recursion needs an explicit stack, which is why recursion reads better.
@lru_cache turns exponential recursion into linear — the most valuable single line in this topic.
Run it in Python
Factorial with its frames printed as they are pushed and popped, then the same problem written as a loop, then the recursion limit hit on purpose — because a stack overflow is much easier to understand once you have caused one.
recursion.pyPython 3
# Recursion, and the stack that makes it work.
import sys
def factorial(n, depth=0):
pad = "| " * depth
print(f"{pad}call factorial({n})")
if n <= 1: # base case: stop, do not recurse
print(f"{pad}return 1")
return 1
result = n * factorial(n - 1, depth + 1) # frame waits here
print(f"{pad}return {n} * {result // n} = {result}")
return result
print(factorial(4))
# The same computation with no stack at all.
def factorial_loop(n):
result = 1
for i in range(2, n + 1):
result *= i
return result
print()
print("iterative:", factorial_loop(4))
# --- what the stack costs ----------------------------------------------
def depth_reached(n):
"""How deep can we go before Python refuses?"""
try:
return 1 + depth_reached(n + 1)
except RecursionError:
return 0
print()
print("Python's recursion limit:", sys.getrecursionlimit())
print("frames we actually got :", depth_reached(0))
print("Each frame holds arguments, locals and a return address. That is memory,")
print("and it is why deep recursion is a space cost, not just a style choice.")
# --- the cost of recomputing -------------------------------------------
calls = 0
def fib(n):
global calls
calls += 1
return n if n < 2 else fib(n - 1) + fib(n - 2)
print()
for n in (10, 20, 25):
calls = 0
value = fib(n)
print(f"fib({n}) = {value:>6} after {calls:>7} calls")
print("Calls roughly double per +1. The tree of frames is the problem, and")
print("memoisation - see the dynamic programming module - is the fix.")
Output
How the code works
if n <= 1: return 1The base case, and the only thing standing between this function and a crash. Every recursive function needs one, and every call must make measurable progress towards it.
result = n * factorial(n - 1, depth + 1)The multiplication happens after the recursive call returns, so the frame has to stay alive while the whole subtree below it runs. That is precisely what the call stack is holding.
the indented print pairsEach call line has a matching return at the same indent. Read downwards for the pushes and upwards for the pops — the output is the stack, drawn over time.
except RecursionError: return 0Python caps the depth deliberately, because the real C stack underneath would otherwise be overrun and the process would die rather than raise. The limit is a guard rail, not the actual capacity.
calls += 1 in fibNaive fib recomputes the same subproblems exponentially often. Recursion is not slow; recursion without memory is.
Change one thing
Delete the base case from factorial. The RecursionError traceback is what an infinite recursion looks like from the inside.
Call fib(30) and then fib(32). Roughly four times the calls for two more terms — and it is about to get much worse.
Rewrite factorial so the recursive call is the last thing it does (pass the accumulator down). That is tail recursion — and CPython still will not optimise it away.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
What does a stack frame hold?
That is why recursion depth is a memory cost: a thousand pending calls means a thousand of these alive at once.
In 'return n * factorial(n - 1)', why can the frame not be discarded at the recursive call?
Pending work after the call is exactly what keeps a frame alive. Writing it so the call is the last thing done is tail recursion - which CPython still will not optimise away.
The program prints call counts for naive fib. What is the shape?
177 calls for fib(10) and 242,785 for fib(25). Recursion is not slow; recursion that recomputes the same subproblems is.
Cheat sheet
Recursion and the Call Stack
A function that calls itself is not magic — it is stack frames piling up and unwinding. Watch them build, watch the answers come back, and watch naive Fibonacci explode into thousands of redundant calls.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.