Recursion is a technique where a function calls itself to solve a smaller version of the same problem. Every recursive solution has two parts:
Each recursive call is pushed onto the call stack. When the base case is reached, the calls unwind and return their results back up the chain.
Factorial of n (written n!) = n x (n-1) x (n-2) x ... x 1. Base case: 0! = 1.
#include <stdio.h>
long long factorial(int n) {
if (n == 0 || n == 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main() {
for (int i = 0; i <= 10; i++) {
printf("%2d! = %lld\n", i, factorial(i));
}
return 0;
}
/*
Call trace for factorial(4):
factorial(4) -> 4 * factorial(3)
factorial(3) -> 3 * factorial(2)
factorial(2) -> 2 * factorial(1)
factorial(1) -> 1 (base case)
factorial(2) -> 2 * 1 = 2
factorial(3) -> 3 * 2 = 6
factorial(4) -> 4 * 6 = 24
*/#include <stdio.h>
long long factorial(int n) {
long long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
int main() {
for (int i = 0; i <= 10; i++) {
printf("%2d! = %lld\n", i, factorial(i));
}
return 0;
}
/*
Iterative is generally faster (no function call overhead)
and safer (no stack overflow risk for large n).
*/Fibonacci: F(0)=0, F(1)=1, F(n) = F(n-1) + F(n-2). This is a classic example that shows both the elegance and the inefficiency of naive recursion - it recalculates the same values many times.
#include <stdio.h>
// Naive: O(2^n) - exponential time, very slow for large n
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
for (int i = 0; i <= 10; i++) {
printf("fib(%2d) = %d\n", i, fib(i));
}
return 0;
}
/*
fib(5) call tree (shows repeated work):
fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2) -> computed again!
│ │ └── fib(1)
│ └── fib(2) -> computed again!
└── fib(3) -> computed again!
*/#include <stdio.h>
#define MAX 100
long long memo[MAX]; // cache array, initialized to -1
long long fib(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // return cached result
memo[n] = fib(n - 1) + fib(n - 2); // compute and cache
return memo[n];
}
int main() {
for (int i = 0; i < MAX; i++) memo[i] = -1; // init cache
for (int i = 0; i <= 15; i++) {
printf("fib(%2d) = %lld\n", i, fib(i));
}
return 0;
}
// Memoized: O(n) - each value computed only onceTower of Hanoi is the perfect recursion problem. Move n disks from source peg to destination peg using an auxiliary peg, with the rule that a larger disk can never be placed on a smaller one.
#include <stdio.h>
void hanoi(int n, char from, char to, char aux) {
if (n == 1) {
printf("Move disk 1 from %c to %c\n", from, to);
return;
}
hanoi(n - 1, from, aux, to); // move n-1 disks to aux
printf("Move disk %d from %c to %c\n", n, from, to);
hanoi(n - 1, aux, to, from); // move n-1 disks from aux to dest
}
int main() {
int n = 3;
printf("Tower of Hanoi with %d disks:\n\n", n);
hanoi(n, 'A', 'C', 'B');
return 0;
}
/*
Output:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Total moves for n disks = 2^n - 1
For n=3: 2^3 - 1 = 7 moves
*/| Aspect | Recursion | Iteration |
|---|---|---|
| Code clarity | Cleaner for tree/graph problems | Cleaner for simple loops |
| Performance | Slower (function call overhead) | Faster |
| Memory | Uses call stack (risk of overflow) | Uses constant stack space |
| Best for | Tree traversal, divide & conquer, backtracking | Simple counting, array traversal |
| Debugging | Harder to trace | Easier to trace |
Explore 500+ free tutorials across 20+ languages and frameworks.