Recursion is when a subroutine calls itself as part of its own definition — solving a problem by breaking it into a smaller version of the same problem, until a simple stopping condition (the base case) is reached. It is a powerful idea that mirrors how many real problems naturally decompose.
What is the classic mental model for recursion?
Imagine Russian nesting dolls (matryoshka): open a doll and find a smaller doll inside; open that and find another — until you reach the smallest solid doll that cannot be opened. Recursion works identically: each function call opens to reveal a slightly smaller problem, until the base case (the smallest doll) requires no further opening and the answers fold back outward.
What are the two essential parts of every recursive function?
Every correct recursive function must have exactly two parts:
| Part | Purpose | What happens without it |
|---|---|---|
| Base case | The condition under which the function stops calling itself and returns a direct answer | Without a base case, the function recurses forever → stack overflow |
| Recursive case | The call to the function itself with a simpler input, moving towards the base case | Without progress towards base case → infinite recursion |
The rule: each recursive call must make the problem strictly smaller in some measurable way (e.g. n − 1, half the length of a list) so the base case is inevitably reached.
How does the factorial function use recursion?
The factorial of n (written n!) is defined as:
- 0! = 1 (base case)
- n! = n × (n−1)! for n > 0 (recursive case)
Pseudocode:
FUNCTION factorial(n)
IF n == 0 THEN
RETURN 1
ELSE
RETURN n * factorial(n - 1)
END IF
END FUNCTION
Trace table for factorial(4):
| Call | n | Action | Returns |
|---|---|---|---|
| factorial(4) | 4 | 4 × factorial(3) | waits… |
| factorial(3) | 3 | 3 × factorial(2) | waits… |
| factorial(2) | 2 | 2 × factorial(1) | waits… |
| factorial(1) | 1 | 1 × factorial(0) | waits… |
| factorial(0) | 0 | base case: RETURN 1 | 1 |
| factorial(1) resumes | 1 × 1 | 1 | |
| factorial(2) resumes | 2 × 1 | 2 | |
| factorial(3) resumes | 3 × 2 | 6 | |
| factorial(4) resumes | 4 × 6 | 24 |
The result unwinds — each waiting call receives the answer from the one below it and completes its own multiplication.
What is the call stack during recursion?
Each call to a recursive function pushes a new stack frame onto the call stack. The frame stores the local variable n and the return address (where to come back to). For factorial(4), the stack builds up to 5 frames deep before any are removed.
Stack at deepest point (n=0):
[ factorial(0) ] ← top
[ factorial(1) ]
[ factorial(2) ]
[ factorial(3) ]
[ factorial(4) ] ← bottom
As each base/recursive call returns, its frame is popped. This is why excessive recursion (e.g. factorial(100000)) crashes with a stack overflow — the stack runs out of memory.
How does recursion compare with iteration?
| Feature | Recursion | Iteration (loop) |
|---|---|---|
| Code length | Often shorter and more elegant | Sometimes more verbose |
| Memory use | Uses call stack (can overflow) | Uses constant extra memory |
| Speed | Slight overhead per function call | Generally faster in practice |
| Readability | Natural for tree/fractal structures | Natural for simple repetition |
| Risk | Stack overflow if base case missing | Infinite loop if condition wrong |
Many problems (factorial, tree traversal, quicksort, Fibonacci) can be expressed either way. Recursion shines when the problem structure is itself recursive — for example, a folder containing subfolders containing further subfolders.
What is a real-world use of recursion in computing?
File system traversal: To list every file in a folder and all its subfolders, the algorithm visits a folder's contents, and for each subfolder it encounters, calls itself on that subfolder. The base case is a folder with no subfolders — just files.
Quicksort: Choose a pivot, place all smaller items to the left and larger items to the right, then recursively sort the left and right halves. The base case is a subarray of length 0 or 1 (already sorted).
Parsing expressions: A calculator application parses 3 + (4 × 2) recursively — solving the inner bracketed expression first, then combining the result with the outer operation.
Frequently asked questions
How do I know when to use recursion instead of a loop?
Use recursion when the problem naturally breaks into smaller copies of itself — particularly for tree structures, divide-and-conquer algorithms, and problems defined recursively in mathematics (like factorials and Fibonacci). Use iteration when you simply need to repeat an action a fixed or counted number of times and there is no natural self-similar substructure.
What is infinite recursion and how do I fix it?
Infinite recursion occurs when a recursive function has no reachable base case — either it is missing entirely or the recursive call does not move toward it. The fix is to: (1) ensure a base case exists, and (2) ensure the argument passed to each recursive call is strictly closer to the base case condition. For factorial, n − 1 always decreases toward 0, so it terminates correctly.
Is the Fibonacci sequence a good example of recursion?
It demonstrates the concept clearly, but it is actually a poor practical use of recursion. A naive recursive Fibonacci recalculates the same values repeatedly — fib(38) makes over 100 million calls. This is solved by memoisation (caching results) or by converting to iteration. At GCSE, Fibonacci is taught as an example of the recursive pattern, not as a model of efficient coding.
What does "unwinding the stack" mean?
When a recursive function reaches its base case, it returns a value. The calling function (one level up the stack) resumes, uses that value, and returns its own result to the function that called it. This process of frames being popped and results passing upward is called unwinding the stack. In the factorial example, the 1 returned by factorial(0) triggers a chain of multiplications as each frame unwinds in turn.
Build real intuition for recursion through Socratic dialogue with Professor Turing at aitutors.me.