Recursion
A function that calls itselfA recursive function solves a problem by calling itself on a smaller piece of it — until it reaches a piece so small that the answer is obvious: the base case. In the lab below you watch the call stack grow and unwind, see the Fibonacci call tree explode, solve the Tower of Hanoi, and find out what happens when the base case is missing.
- Base casestops the calls
- Recursive casea smaller version of the same problem
- Stackgrows down, then unwinds
Ready
Keyboard: ← → step · Space play / pause · R reset · Esc exit classroom mode
The ideas behind the lab
Exactly what you watched happen, in plain steps.
Every recursive function has two parts
The base case answers the smallest version of the problem directly, without calling again — it is what stops the recursion. The recursive case reduces the problem (n becomes n − 1, n / 10, a shorter list …) and calls the same function on the smaller piece, trusting it to return the right answer. Each call gets its own stack frame, so every call has its own n.
long long fact(int n)
{
if (n <= 1) // base case: the answer is known
return 1;
return n * fact(n - 1); // recursive case: a smaller problem
}
// fact(4) = 4 * fact(3) = 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1) = 24
| Problem | Base case | Recursive case | Example |
|---|---|---|---|
| Factorial | fact(1) = 1 | fact(n) = n × fact(n − 1) | fact(5) = 120 |
| Power | power(b, 0) = 1 | power(b, e) = b × power(b, e − 1) | power(2, 10) = 1024 |
| Sum of digits | n < 10 → n | n % 10 + sum(n / 10) | sum(4096) = 19 |
| Fibonacci | fib(0) = 0, fib(1) = 1 | fib(n − 1) + fib(n − 2) | fib(10) = 55 |
| GCD (Euclid) | gcd(a, 0) = a | gcd(b, a % b) | gcd(48, 18) = 6 |
| Tower of Hanoi | 0 disks: do nothing | move n − 1, move 1, move n − 1 | 2ⁿ − 1 moves |
Winding and unwinding
- Every call pushes a new frame with its own parameters on the stack.
- The calls go deeper and deeper until the base case is reached.
- The base case returns a value without calling again.
- Then the frames return one by one, each finishing its own calculation.
- Code before the recursive call runs on the way down; code after it runs on the way back up.
Writing a recursive function
- Find the smallest case whose answer you know — write it first.
- Describe the answer for n using the answer for a smaller problem.
- Make sure every call gets closer to the base case.
- Trust the recursive call: assume it returns the right answer.
- Trace a small example (n = 3) on paper with the stack frames.
Recursion vs loops
- Anything written with recursion can also be written with a loop.
- Recursion is natural for problems that split into smaller copies (trees, Hanoi, sorting).
- Each call costs time and stack memory; loops are usually faster.
- Too deep a recursion (or a missing base case) overflows the stack and crashes.
- Naive fib(n) repeats work exponentially — the loop version is far quicker.
Sum of digits, and a countdown on the way down
Every line, explained.
#include <stdio.h>
int sumDigits(int n)
{
if (n < 10) return n;
Base case: a single digit is its own sum.
return n % 10 + sumDigits(n / 10);
The last digit + the sum of the other digits.
}
void countdown(int n)
{
if (n == 0) {
Base case.
printf("Go!\n");
return;
A void function can stop with a plain return.
}
printf("%d ", n);
Runs BEFORE the call, so on the way down.
countdown(n - 1);
A smaller problem.
}
int main(void)
{
printf("%d\n", sumDigits(4096));
6 + sum(409) = 6 + 9 + sum(40) = … prints 19
countdown(3);
Prints 3 2 1 Go!
return 0;
}
Spot the bug
Mistakes almost every beginner makes — and how to fix them.
No base case
int fact(int n)
{
return n * fact(n - 1);
}
int fact(int n)
{
if (n <= 1) return 1;
return n * fact(n - 1);
}
Nothing stops the calls: the stack fills up and the program crashes with a stack overflow (segmentation fault).
Not getting closer to the base case
return n * fact(n); // same n again
return n * fact(n - 1); // smaller each time
Every recursive call must make the problem smaller, or the base case is never reached.
A base case that can be jumped over
if (n == 1) return 1; … // fact(0) never stops
if (n <= 1) return 1;
fact(0) skips n == 1 and goes to -1, -2 … Use a condition that catches every small value.
Forgetting to return the recursive result
if (n < 10) return n; n % 10 + sumDigits(n / 10); // result lost
if (n < 10) return n; return n % 10 + sumDigits(n / 10);
The value of the recursive call must be passed back up with return, at every level.
Using naive recursion for big Fibonacci numbers
fib(45) // about 3.6 billion calls
// loop: a = 0, b = 1, slide 45 times // or remember results already found
fib(n) calls itself twice, so the work roughly doubles with each n. A loop needs only n rounds.
Check your understanding
Answer each question — you will see the explanation straight away.
What stops a recursive function from calling itself forever?
The base case returns without calling again.
int f(int n) { if (n == 0) return 0; return n + f(n - 1); } — f(4) is?
4 + 3 + 2 + 1 + 0 = 10.
While fact(1) runs (called from main as fact(4)), how many fact frames are on the stack?
fact(4), fact(3), fact(2) and fact(1) — four frames.
What happens to a recursive function with no base case?
Frames pile up until the stack memory is full.
How many moves does the Tower of Hanoi need for 3 disks?
2³ − 1 = 7 moves.
Recursion quiz
Test yourself: 10 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.