C Recursion
Introduction to Recursion
Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller subproblems. Each recursive call works on a smaller instance of the same problem until it reaches a base case that can be solved directly.
Recursion is particularly useful for problems that have natural recursive structures like tree traversals, mathematical sequences, and divide-and-conquer algorithms.
Components of Recursion
| Component | Description | Purpose |
|---|---|---|
| Base Case | The simplest instance that can be solved directly | Prevents infinite recursion and provides termination |
| Recursive Case | The function calls itself with modified parameters | Breaks problem into smaller subproblems |
| Progress | Each call moves toward the base case | Ensures the recursion eventually terminates |
Factorial Example (with Input Guard)
Example
#include <stdio.h>
unsigned long long factorial(int n) {
if (n < 0) {
// Not defined for negative integers
return 0ULL;
}
if (n <= 1) {
return 1ULL; // base case
}
return (unsigned long long)n * factorial(n - 1); // recursive case
}
int main(void) {
int number = 5;
unsigned long long f = factorial(number);
if (f == 0ULL && number < 0) {
printf("Factorial undefined for negatives\n");
} else {
printf("Factorial of %d is %llu\n", number, f);
printf("Calculation steps: ");
printf("factorial(5) = 5 * factorial(4) ");
printf("factorial(4) = 4 * factorial(3) ");
printf("factorial(3) = 3 * factorial(2) ");
printf("factorial(2) = 2 * factorial(1) ");
printf("factorial(1) = 1 (base case)\n");
}
return 0;
}Output
Factorial of 5 is 120 Calculation steps: factorial(5) = 5 * factorial(4) factorial(4) = 4 * factorial(3) factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1) factorial(1) = 1 (base case)
ℹ️ Note: Each recursive call creates a new stack frame with its own parameters and local variables.
Fibonacci Sequence (Naive Recursion)
⚠️ Warning: This naive approach has exponential time complexity (≈O(ϕ^n)). For large n, prefer an iterative loop or memoization.
Example
#include <stdio.h>
int fibonacci(int n) {
if (n <= 0) return 0; // base cases
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2); // recursive case
}
int main(void) {
printf("Fibonacci sequence: ");
for (int i = 0; i < 10; i++) {
printf("%d ", fibonacci(i));
}
printf("\n");
return 0;
}Output
Fibonacci sequence: 0 1 1 2 3 5 8 13 21 34
Efficient Fibonacci (Iterative)
Example
#include <stdio.h>
int fib_iter(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
int a = 0, b = 1; // F(0), F(1)
for (int i = 2; i <= n; i++) {
int c = a + b;
a = b;
b = c;
}
return b;
}
int main(void) {
for (int i = 0; i < 10; i++) {
printf("%d ", fib_iter(i));
}
printf("\n");
return 0;
}Output
0 1 1 2 3 5 8 13 21 34
ℹ️ Note: The iterative version runs in O(n) time with O(1) extra space.
Recursion vs Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Readability | Often more elegant for recursive problems | Can be more straightforward for simple loops |
| Memory | Uses call stack; deep recursion can overflow | Often uses constant stack space |
| Performance | Function call overhead | Generally faster (no call overhead) |
| Use Case | Trees, backtracking, divide-and-conquer | Counters, linear scans, accumulations |
Tail Recursion (and a Wrapper)
Tail recursion occurs when the recursive call is the last operation in the function. Some compilers can optimize it into a loop (tail-call optimization), but the C standard does not guarantee this optimization.
Example
#include <stdio.h>
unsigned long long factorialTR_helper(int n, unsigned long long acc) {
if (n <= 1) return acc; // base case
return factorialTR_helper(n - 1, acc * (unsigned long long)n); // tail call
}
unsigned long long factorialTail(int n) {
if (n < 0) return 0ULL; // guard
return factorialTR_helper(n, 1ULL);
}
int main(void) {
printf("Tail recursive factorial(5): %llu\n", factorialTail(5));
return 0;
}Output
Tail recursive factorial(5): 120
ℹ️ Note: Do not rely on tail-call optimization for portability; convert to an explicit loop if stack usage is a concern.
Divide & Conquer: Recursive Binary Search
Binary search divides the search range in half each step, naturally fitting a recursive pattern.
Example
#include <stdio.h>
int bsearch_rec(const int *a, int left, int right, int key) {
if (left > right) return -1; // base case: not found
int mid = left + (right - left) / 2;
if (a[mid] == key) return mid; // base case: found
if (a[mid] > key) return bsearch_rec(a, left, mid - 1, key);
return bsearch_rec(a, mid + 1, right, key);
}
int main(void) {
int sorted[] = {2, 5, 7, 9, 12, 15, 21};
int n = (int)(sizeof sorted / sizeof *sorted);
int idx = bsearch_rec(sorted, 0, n - 1, 12);
printf("Index of 12: %d\n", idx);
return 0;
}Output
Index of 12: 4
Mutual Recursion
Two or more functions can call each other recursively. Ensure all paths converge to a base case.
Example
#include <stdio.h>
int is_even(int n); // forward declarations
int is_odd(int n);
int is_even(int n) {
if (n == 0) return 1; // base
if (n < 0) n = -n; // progress toward base
return is_odd(n - 1);
}
int is_odd(int n) {
if (n == 0) return 0; // base
if (n < 0) n = -n;
return is_even(n - 1);
}
int main(void) {
printf("7 is odd? %s\n", is_odd(7) ? "yes" : "no");
printf("10 is even? %s\n", is_even(10) ? "yes" : "no");
return 0;
}Output
7 is odd? yes 10 is even? yes
Stack Depth & Safety
- Always define a clear base case and make measurable progress toward it.
- Beware of deep recursion causing stack overflow—prefer iteration for very deep computations.
- Validate inputs (e.g., negative factorial) to avoid unbounded recursion.
- Avoid heavy work after the recursive call if you hope for tail-call optimization.
- For overlapping subproblems (like Fibonacci), use memoization or convert to iteration.