Recursion
Recursion: the programming technique that looks simple until you understand it. And then too.
What if a function could solve a problem by asking a slightly simpler version of itself for help — over and over, until the answer is trivially obvious? That is recursion.
The developer Q&A platform "Stack Overflow" was named after exactly the crash that happens when a recursion never ends. That is how well known this crash is among programmers.
The Self-Calling Function
Definition
Recursion
Analogy
Definition
The Matryoshka analogy breaks in two places. A set of dolls always has a smallest doll; a recursion without a base case lacks one, and the opening goes on forever until memory runs out or, as in Python, the recursion limit kicks in. And while a person simply remembers their contribution, in a program each stack frame has to explicitly store its state (parameters, local variables) while it waits for the result from the call below.
Example: Factorial (5!) — Descent and Return
- 1. factorial(5) calls factorial(4) — remembers 5 * ?
- 2. factorial(4) calls factorial(3) — remembers 4 * ?
- 3. factorial(3) calls factorial(2) — remembers 3 * ?
- 4. factorial(2) calls factorial(1) — remembers 2 * ?
- 5. factorial(1) reaches BASE CASE → returns 1
- 6. factorial(2) = 2 * 1 = 2
- 7. factorial(3) = 3 * 2 = 6
- 8. factorial(4) = 4 * 6 = 24
- 9. factorial(5) = 5 * 24 = 120
At peak depth, 5 stack frames exist simultaneously in memory, each with its own copy of n. When the base case returns, frames are removed one by one in reverse order — the so-called "unwinding."
Note
Python Code: Factorial
def factorial(n):
if n <= 1: # Base case
return 1
return n * factorial(n - 1) # Recursive case
print(factorial(5)) # Output: 120The Base Case: Your Safety Net
The base case is the single most critical line in any recursive function. It defines WHEN the function stops calling itself and WHAT it returns at that point. Without a base case, the function calls itself infinitely — each call adds a stack frame until available memory is exhausted or, as in Python, a fixed recursion limit kicks in.
Imagine a circular maze with no exit signs. Without a marker, a person wanders endlessly in circles. Place a red marker at one specific spot with the instruction "When you see the red marker, stop walking" — and infinite wandering becomes a finite search. That marker is the base case.
Note
Countdown: Without vs. With Base Case
# BROKEN — no base case
def countdown(n):
print(n)
countdown(n - 1) # calls forever: 3, 2, 1, 0, -1, ...
# → RecursionError after ~1000 calls
# CORRECT — base case stops at 0
def countdown(n):
if n <= 0: # Base case
print(0)
return # STOP
print(n)
countdown(n - 1) # Recursive caseThe difference is a single if check — but it decides between a working program and a crash. The base case must appear BEFORE the recursive call in the function body.
Caution
Common Mistake: Increasing the Recursion Limit
sys.setrecursionlimit(10000) does not add more memory. With endless recursion it only delays the crash, and a limit set too high can crash Python itself. If the recursion runs forever or the problem requires very deep recursion, the real fix is either a proper base case or switching to an iterative approach.
Where Loops Fail: Recursion for Hierarchies
Loops (for, while) excel at processing linear sequences: iterate through a list, count from 1 to n. But when the data structure itself is nested to unknown depth — folders within folders, HTML elements within elements, branches of a game tree — a simple loop cannot see deeper than one level.
You need to find all .pdf files on a hard drive. Checking each file in the top-level folder is easy. But some items are folders containing more files and folders, nested to unknown depth. The recursive approach: "Open the folder. Check each item. If it is a file, evaluate it. If it is a folder, apply the same procedure to it."
def find_pdfs(folder): results = [] for item in os.listdir(folder): path = os.path.join(folder, item) if os.path.isfile(path) and path.endswith('.pdf'): results.append(path) elif os.path.isdir(path): results.extend(find_pdfs(path)) return results Shorter, reads like the problem description. Uses the call stack implicitly.
def find_pdfs_iterative(root): results = [] stack = [root] while stack: folder = stack.pop() for item in os.listdir(folder): path = os.path.join(folder, item) if os.path.isfile(path) and path.endswith('.pdf'): results.append(path) elif os.path.isdir(path): stack.append(path) return results Avoids Python's recursion limit for very deep directories.
Note
Recursion in the Wild
Interactive: Fibonacci Call Tree
Step through the call tree of fib(5). Observe how the function keeps calling itself until it reaches a base case — and how the results then travel back up the tree. Pay special attention to the fact that fib(3) is computed twice and fib(2) is called three times.
Note
Synthesis: Recursion Is Not Magic
Recursion is not magic — it is a disciplined delegation pattern: break the problem down, trust your future self to handle the smaller piece, and define the point where delegation stops.
In AI, recursion is everywhere: tree traversals, depth-first search (DFS), divide-and-conquer algorithms, and game-tree evaluation (MinMax) — all are built on the recursive principle.
Note
Key Takeaways
- Recursion = a function calls itself to reduce a problem to a smaller version of the same problem.
- Every recursive function needs two parts: the base case (when to stop) and the recursive case (how to continue).
- Without a base case: infinite calls → stack overflow (in Python: RecursionError). The base case is the safety net.
- Recursion is ideal for hierarchical problems (folders, trees, nested structures) where the depth is unknown.
- Recursion and iteration can solve the same problems, but recursion maps hierarchical problems more naturally.
Check
Quiz: Recursion
What are the two essential parts of every recursive function?
Select one answer
1. What are the two essential parts of every recursive function?
2. factorial(4) is called. How many stack frames exist at peak depth?
3. A countdown function has no base case. What happens when you call countdown(3)?
4. You need to find all .txt files in a folder with subfolders of unknown depth. Why is recursion better suited than a simple for loop?
Check
Checkpoint: Test Your Knowledge
Can you explain this in your own words? Tick what you've got.
0 of 3 done