Recursion is a programming technique in which a function calls itself as part of its own definition, solving a problem by reducing it to a smaller instance of the same problem, with a base case that terminates the chain of self-calls and returns a concrete value without further recursion.
Functions that call themselves
What you'll learn: The two required parts of a recursive function (base case + recursive case). How the call stack grows and shrinks. Where recursion is genuinely useful vs where a loop is clearer.
How to read this tab: Trace through the recursive factorial example by hand on paper before reading the explanation. Write out each function call and return value. The visual call stack diagram will then make immediate sense.
Recursion is solving a big problem by solving a slightly smaller version of the same problem, then using that to solve the original — until the problem is so small it answers itself.
Every recursive function must have both — or it loops forever. The base case: a condition where the function returns immediately without calling itself. The recursive case: a call to itself with a smaller or simpler input. The classic mistake: forgetting the base case and hitting Python's recursion limit. Before writing a recursive function, identify the base case first.
The two required parts
Every recursive function needs two things or it runs forever: a base case that returns directly, and a recursive case that calls the function with a smaller input.
def factorial(n):
if n == 0: # BASE CASE: 0! = 1
return 1
return n * factorial(n - 1) # RECURSIVE CASE: n! = n*(n-1)!
print(factorial(5)) # 120
# factorial(5) = 5 * factorial(4)
# factorial(4) = 4 * factorial(3)
# ...
# factorial(0) = 1 ← unwinds back upTrace recursion on paper — the "unwinding" phase surprises beginners. factorial(4) calls factorial(3) calls factorial(2) calls factorial(1) — the stack grows. factorial(1) returns 1. factorial(2) returns 2*1=2. factorial(3) returns 3*2=6. factorial(4) returns 4*6=24. The stack unwinds, computing the result on the way back up. Many recursive algorithms accumulate results during the unwind phase.
The call stack grows then shrinks
Each recursive call pushes a new frame. All frames accumulate until the base case, then unwind — each frame completes its calculation and pops. A recursion 5 levels deep uses 5 stack frames simultaneously. No base case = infinite frames = stack overflow.
Forgetting the base case, or a base case that is never reached, causes infinite recursion and a stack overflow. Python's default limit is 1000 recursive calls.
Recursion shines on recursive data structures. Trees, graphs, and nested structures are naturally recursive — a tree is a node with children that are trees. Traversal, search, and transformation of these structures map directly to recursive functions. For flat sequences (lists, strings), a loop is almost always cleaner and faster than recursion in Python.
Where recursion is natural
Problems with self-similar structure: tree traversal (visit root, then recursively visit subtrees), merge sort (divide in half, sort each half recursively, combine), filesystem traversal (list files in a folder, then recurse into subfolders), Fibonacci (F(n) = F(n-1) + F(n-2)).
In Python, prefer iteration over recursion for flat sequences. Python doesn't optimise tail calls, has a recursion limit, and function calls are slower than loop iterations. Use recursion when it makes the algorithm clearer (tree traversal, divide-and-conquer, backtracking). Use iteration when you're processing a sequence linearly.
Recursion vs. iteration
Any recursive solution can be rewritten iteratively and vice versa. Recursion is elegant for tree-shaped problems. Iteration is often more efficient (no stack overhead) and avoids overflow risk for large inputs.
✅ Beginner tab complete — check your understanding
- I know every recursive function needs a base case (when to stop) and a recursive case (how to reduce the problem)
- I can trace through a simple recursive function (factorial, fibonacci) by hand
- I know Python has a recursion limit of ~1000 levels and raises RecursionError when exceeded
Memoisation, tail recursion, and mutual recursion
What you'll learn: Memoisation — caching results to fix exponential naive recursion (fibonacci). Tail recursion and why Python doesn't optimise it. Mutual recursion — two functions calling each other.
How to read this tab: Implement naive fibonacci, measure how slow it is for fib(40), then add @functools.lru_cache and measure again. The performance difference — millions of times faster — demonstrates why memoisation matters.
Naive fibonacci is O(2ⁿ) — catastrophically slow. fib(50) makes over a trillion function calls. Memoisation fixes this by caching results: if fib(30) has been computed, use the cached value instead of recomputing. Python makes this trivially easy: @functools.lru_cache(maxsize=None) above the function definition. This reduces fib(50) to 50 function calls.
Memoisation: fixing exponential recursion
# Naive: O(2^n) — computes fib(n-2) exponentially many times
def fib_naive(n):
if n <= 1: return n
return fib_naive(n-1) + fib_naive(n-2)
# Memoised: O(n) — cache results to avoid recomputation
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1: return n
return fib(n-1) + fib(n-2)
print(fib(100)) # instant — memoisation is the basis of dynamic programmingPython deliberately doesn't optimise tail calls. A tail call is a recursive call as the last operation in a function — no work to do after the recursive call returns. Languages like Scheme, Haskell, and Scala optimise tail calls to not use extra stack space (tail call optimisation / TCO). Python's creator Guido van Rossum explicitly chose not to implement TCO, arguing it makes stack traces harder to read.
Tail recursion
A tail-recursive function has the recursive call as its last operation. TCO can replace the caller's frame with the callee's, giving O(1) stack usage. Scheme guarantees it. Python does not implement it — tail-recursive Python still risks overflow.
# NOT tail-recursive (multiply n after return)
def factorial(n):
if n == 0: return 1
return n * factorial(n-1)
# Tail-recursive (accumulator pattern)
def factorial_tail(n, acc=1):
if n == 0: return acc
return factorial_tail(n-1, acc*n) # last operationMutual recursion: A calls B, B calls A. Example: def is_even(n): return True if n==0 else is_odd(n-1) and def is_odd(n): return False if n==0 else is_even(n-1). Each function calls the other. This works in Python but is inefficient for large n. In functional languages, mutual recursion is more common and compilers often optimise it.
Mutual recursion
A calls B which calls A. Example: is_even(n) returns True if n==0, else calls is_odd(n-1). C requires forward declarations for mutual recursion.
✅ Intermediate tab complete — check your understanding
- I can use @functools.lru_cache to memoise a recursive function
- I know naive fibonacci is O(2ⁿ); memoised fibonacci is O(n)
- I know Python deliberately does NOT do tail call optimisation (Guido van Rossum's decision)
- I can recognise mutual recursion: function A calls B, B calls A
Primitive recursion, the Ackermann function, and structural induction
What you'll learn: Primitive recursive functions (the class of functions computable without unbounded loops). The Ackermann function — computable but not primitive recursive. Structural induction for proving recursive programs correct.
How to read this tab: Read when studying computability theory or formal methods.
Primitive recursion and the Ackermann function
Primitive recursive functions are computable by bounded recursion — depth is a function of the input, ensuring termination. The Ackermann function (Wilhelm Ackermann, 1928) is total and computable but not primitive recursive — it grows faster than any primitive recursive function. For inputs (4,2) it produces a number with 19,728 digits. It demonstrates that general recursion is strictly more powerful than bounded recursion.
Structural induction for correctness proofs
Proving recursive correctness uses structural induction: (1) base case — prove the base case is correct; (2) inductive step — assuming correctness for all inputs smaller than n, prove correctness for n. The correctness of factorial(n): base: factorial(0) = 1 = 0! ✓. Inductive: assume factorial(k) correct for k < n. Then factorial(n) = n * factorial(n-1) = n * (n-1)! = n! ✓.
Knuth, D. E. (1997). TAOCP Vol. 1, §1.2.1 — Mathematical induction. Ackermann, W. (1928). Mathematische Annalen, 99, 118–133. Python recursion limit: docs.python.org/3/library/sys.html.
✅ Expert tab complete
- I know the Ackermann function grows faster than any primitive recursive function
- I can use structural induction to prove a property of a recursive function