Recursion
A recursive function calls itself. It solves a problem by solving a smaller copy of the same problem, until the problem is so small that the answer is obvious. Every recursive function has two parts:
- a base case: the smallest problem, answered directly, which stops the recursion;
- a recursive case: the function calls itself on a smaller problem, and builds its answer from the result.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case: a smaller problem
}
int main() {
for (int i = 1; i <= 6; i++) {
printf("%d! = %d\n", i, factorial(i));
}
return 0;
}4! is 4 × 3!, and 3! is 3 × 2!, and so on, down to 1! = 1, which needs no further work.
Tracing the calls
Each call waits for the one it made to finish. factorial(4) unfolds like this:
| Step | Call | Waiting for | Returns |
|---|---|---|---|
| 1 | factorial(4) | 4 * factorial(3) | |
| 2 | factorial(3) | 3 * factorial(2) | |
| 3 | factorial(2) | 2 * factorial(1) | |
| 4 | factorial(1) | nothing: base case | 1 |
| 5 | back in factorial(2) | 2 × 1 = 2 | |
| 6 | back in factorial(3) | 3 × 2 = 6 | |
| 7 | back in factorial(4) | 4 × 6 = 24 |
The calls go down until the base case, then the answers come back up, each multiplied in on the way.
The call stack
Every call gets its own stack frame: a fresh set of parameters and local variables, piled on top of the caller's. While factorial(1) runs there are four frames, each with its own n (4, 3, 2 and 1). When a call returns, its frame is removed and the caller carries on exactly where it stopped.
That's why a recursive function needs no special tricks to "remember" where it was: each unfinished call is still on the stack. It's also why recursion has a limit. The stack is small (often 1 to 8 MB), and a recursion that goes too deep, or never reaches its base case, fills it and crashes the program with a stack overflow (on Linux, a "segmentation fault").
Before or after the call
Whether work happens before or after the recursive call changes the order:
#include <stdio.h>
void countDown(int n) {
if (n == 0) return;
printf("%d ", n); // before the call: on the way down
countDown(n - 1);
}
void countUp(int n) {
if (n == 0) return;
countUp(n - 1);
printf("%d ", n); // after the call: on the way back up
}
int main() {
countDown(5);
printf("\n");
countUp(5);
printf("\n");
return 0;
}countUp prints nothing until the deepest call returns, so the numbers come out in increasing order. The same idea prints a number's binary digits in the right order, as you'll see below.
Classic recursive programs
Sum of digits, power and GCD
#include <stdio.h>
int digitSum(int n) {
if (n < 10) return n; // one digit: the sum is the digit
return n % 10 + digitSum(n / 10);
}
// x to the power n, halving n each time: about log2(n) calls instead of n
long long power(long long x, int n) {
if (n == 0) return 1;
long long half = power(x, n / 2);
if (n % 2 == 0) return half * half;
return half * half * x;
}
int gcd(int a, int b) {
if (b == 0) return a; // Euclid: gcd(a, 0) is a
return gcd(b, a % b);
}
int main() {
printf("%d\n", digitSum(98765));
printf("%d\n", (int) power(3, 13));
printf("%d\n", gcd(84, 36));
return 0;
}power uses x¹³ = (x⁶)² × x, and x⁶ = (x³)², so it needs 5 calls instead of 13 multiplications; for x¹⁰⁰⁰ it needs about 11.
Reversing a string
#include <stdio.h>
#include <string.h>
void reverse(char s[], int left, int right) {
if (left >= right) return; // met in the middle: done
char t = s[left];
s[left] = s[right];
s[right] = t;
reverse(s, left + 1, right - 1); // the inside is a smaller problem
}
int main() {
char word[] = "recursion";
reverse(word, 0, strlen(word) - 1);
printf("%s\n", word);
return 0;
}Decimal to binary
#include <stdio.h>
void binary(int n) {
if (n > 1) binary(n / 2); // print the higher bits first...
printf("%d", n % 2); // ...then this one, on the way back up
}
int main() {
int values[4] = {5, 13, 156, 1024};
for (int i = 0; i < 4; i++) {
printf("%d: ", values[i]);
binary(values[i]);
printf("\n");
}
return 0;
}The loop version had to store the bits in an array and print them backwards; the recursion's way back up does the reversing for free.
Binary search
Searching a sorted array: look at the middle, and recurse into whichever half can contain the value. Each call halves the range:
#include <stdio.h>
int search(int a[], int low, int high, int target) {
if (low > high) return -1; // empty range: not found
int mid = (low + high) / 2;
if (a[mid] == target) return mid;
if (a[mid] < target) return search(a, mid + 1, high, target);
return search(a, low, mid - 1, target);
}
int main() {
int sorted[10] = {3, 8, 15, 21, 34, 42, 57, 63, 78, 91};
printf("42 is at index %d\n", search(sorted, 0, 9, 42));
printf("50 is at index %d\n", search(sorted, 0, 9, 50));
return 0;
}A million sorted values need at most 20 steps, because 2²⁰ is just over a million.
Tower of Hanoi
Move a stack of disks from peg A to peg C, one disk at a time, never putting a larger disk on a smaller one. The recursive idea is all there is to it: move the top n − 1 disks out of the way to B, move the largest disk to C, then move the n − 1 disks from B onto it.
#include <stdio.h>
void hanoi(int n, char from, char to, char via) {
if (n == 0) return;
hanoi(n - 1, from, via, to);
printf("disk %d: %c -> %c\n", n, from, to);
hanoi(n - 1, via, to, from);
}
int main() {
hanoi(3, 'A', 'C', 'B');
return 0;
}n disks take 2ⁿ − 1 moves: 7 for three disks, and over a million for twenty.
Why naive Fibonacci is slow
The definition fib(n) = fib(n − 1) + fib(n − 2) translates straight into code, but it recomputes the same values again and again:
#include <stdio.h>
int calls = 0;
int fib(int n) {
calls++;
if (n < 2) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
int result = fib(20); // first, so calls is complete before it's printed
printf("fib(20) = %d, using %d calls\n", result, calls);
return 0;
}fib(20) makes 21,891 calls, and each extra step nearly doubles the work: fib(40) would make over 300 million.
The fix for the slowness is memoisation: remember each answer the first time, and look it up after that:
#include <stdio.h>
int memo[50] = {0}; // 0 means "not worked out yet"
int fib(int n) {
if (n < 2) return n;
if (memo[n] != 0) return memo[n]; // already known
memo[n] = fib(n - 1) + fib(n - 2);
return memo[n];
}
int main() {
printf("fib(40) = %d\n", fib(40));
return 0;
}Now each value from 2 to 40 is worked out once: 39 additions instead of hundreds of millions of calls.
Recursion or a loop?
| Recursion | A loop | |
|---|---|---|
| Fits problems that are | naturally self-similar: trees, halving, Hanoi, nested structures | a simple sequence of steps |
| Memory | a stack frame per call | constant |
| Risk | stack overflow if very deep | none of that |
| Speed | a little slower (each call has a cost) | a little faster |
| Readability | often shorter and closer to the definition | often more direct for counting |
Factorial and Fibonacci are clearer as loops in real code; recursion shines when the problem splits into smaller copies of itself, as binary search, Hanoi, sorting algorithms like merge sort and quicksort, and anything shaped like a tree do.
Common mistakes
| Mistake | What happens |
|---|---|
| No base case | the function calls itself forever, until the stack overflows |
A base case that's never reached, such as factorial(-1) with if (n == 1) | the same: n goes -2, -3, ... for ever. n <= 1 is safer |
The recursive call doesn't get smaller, as in f(n) calling f(n) | infinite recursion |
Ignoring the result: factorial(n - 1); without using it | a wrong answer; the recursive result must be returned or combined |
| Very deep recursion on large inputs | stack overflow; use a loop instead |