Recursion
12 min lesson
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- Recursion matters because some problems, like walking a tree or computing factorials, are naturally described in terms of smaller copies of themselves.
- Think of recursion as Russian nesting dolls: to open the whole set you open one doll and find a smaller doll inside, then repeat until you reach the tiny solid doll.
- A base case is the stopping condition that returns a value without calling the function again; without it recursion never ends.
- A recursive case is the part where the function calls itself with a smaller or simpler argument.
- Each call gets its own copy of the parameters and locals, stored on the call stack, which grows with each recursive call.
- The computer pushes each call onto the stack, runs the base case when reached, then unwinds the stack, returning values back up the chain.
- The syntax is: returnType func(params) { if (baseCase) return value; return func(smallerArgs); }.
- A realistic use: computing factorial, summing a list, or walking a directory tree.
- A surprising detail: too many recursive calls can overflow the call stack and crash the program; deep recursion needs care.
- The example program computes factorial and the sum of numbers from 1 to n using recursion, printing each result.
- Every recursive function needs a base case that stops the recursion.
- Make sure each recursive call moves closer to the base case, or you get infinite recursion.
- Recursion uses the call stack, so very deep recursion can overflow.
- Many recursive solutions can also be written with loops; choose the clearer one.
- Recursion is a powerful thinking tool. You are doing excellent work!
#include <stdio.h>
// Recursive factorial: n! = n * (n-1)!
int factorial(int n) {
// Base case: 0! and 1! are both 1, so stop here
if (n <= 1) {
return 1;
}
// Recursive case: call ourselves with a smaller n
return n * factorial(n - 1);
}
// Recursive sum: 1 + 2 + ... + n
int sumTo(int n) {
// Base case: sum up to 0 is 0
if (n <= 0) {
return 0;
}
// Recursive case: add n to the sum of 1..n-1
return n + sumTo(n - 1);
}
int main(void) {
// Compute 5! = 120
printf("5! = %d\n", factorial(5));
// Compute 1 + 2 + 3 + 4 = 10
printf("Sum 1..4 = %d\n", sumTo(4));
return 0;
}What happens: 5! = 120 Sum 1..4 = 10
Breaking it down
Base case
if (n <= 1) return 1;Stops the recursion when the problem is small enough to answer directly. Without it, the function would call itself forever.
Recursive case
return n * factorial(n - 1);Solves the problem by calling itself with a smaller n. The multiplication happens after the inner call returns.
Sum base case
if (n <= 0) return 0;The sum of numbers up to 0 is 0. This is the stopping point for sumTo.
Sum recursive case
return n + sumTo(n - 1);Adds n to the sum of the smaller range. Each call reduces n by 1 until the base case is reached.
A helpful analogy
Recursion is like Russian nesting dolls. To open the whole set, you open one doll and find a smaller doll inside, then repeat. The base case is the tiny solid doll that cannot be opened, which stops the process. Then you close each doll back up on your way out, just like the recursive calls return one by one.
Nesting rules
- 1.Every recursive function must have at least one base case that returns without calling itself.
- 2.Each recursive call must use a smaller or simpler argument so the base case is eventually reached.
- 3.Avoid recursion when the depth could be very large; the call stack is limited.
- 4.Recursive functions can be slower than loops because of function call overhead.
Common mistakes
Missing base case
Avoid
int f(int n) { return n * f(n - 1); }Use instead
int f(int n) { if (n <= 1) return 1; return n * f(n - 1); }Without a base case the function never stops, the stack grows until it overflows, and the program crashes.
Not moving toward the base case
Avoid
int f(int n) { if (n == 0) return 0; return f(n); }Use instead
int f(int n) { if (n == 0) return 0; return f(n - 1); }If the argument never changes, the base case is never reached. Make sure each call gets smaller or simpler.
Deep recursion on a large n
Avoid
factorial(1000000); // stack overflowUse instead
use a loop for very large inputsEach call uses stack space, and the stack is limited. Deep recursion crashes; a loop uses constant space.
Quick tips
- •Write the base case first, then the recursive case.
- •Trace small values by hand, like factorial(3), to see how the calls unwind.
- •Print the argument at the start of each call while debugging to see the recursion depth.
- •Try changing factorial(5) to factorial(6) and predict the new result before running.
- •Remember that many recursive solutions can be rewritten as loops if depth is a concern.