C Recursion
Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive function needs a base case that stops the recursion, or it will call itself forever.
Recursion is elegant for problems like factorials, Fibonacci numbers, and tree traversal, but each call uses stack memory, so very deep recursion can cause a stack overflow.
int func(int n) {
if (baseCase) return value;
return func(smaller n);
}Base case and recursive case
The base case is the simplest scenario that returns directly without recursing. The recursive case breaks the problem down and calls the function again with a smaller input, moving toward the base case.
Recursion vs iteration
Anything recursion can do, a loop can also do, and often with better performance since loops avoid function call overhead. Recursion is chosen when it makes the solution's logic clearer.
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int main() {
printf("%d\n", factorial(5));
return 0;
}120factorial(5) calls factorial(4), and so on, until reaching the base case n <= 1.
#include <stdio.h>
int fib(int n) {
if (n <= 1) return n;
return fib(n - 1) + fib(n - 2);
}
int main() {
printf("%d\n", fib(6));
return 0;
}8fib(6) recursively sums the two preceding Fibonacci numbers until reaching base cases.
Key points
- Every recursive function needs at least one base case.
- Recursion breaks problems into smaller subproblems of the same type.
- Deep recursion can cause a stack overflow.
- Any recursive solution can usually be rewritten as an iterative loop.