C++ Recursion
What is Recursion?
Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem.
A recursive function has two essential parts:
- Base case(s): A condition that terminates the recursion
- Recursive case: The function calls itself with modified parameters
Basic Recursion Example
#include <iostream>
// Recursive factorial with input validation
long long factorial(int n) {
if (n < 0) { // Guard against invalid domain
throw std::invalid_argument("factorial: negative input");
}
if (n <= 1) // Base case
return 1;
return static_cast<long long>(n) * factorial(n - 1); // Recursive case
}
int main() {
try {
int num = 5;
std::cout << "Factorial of " << num << " is " << factorial(num);
} catch (const std::exception& e) {
std::cout << e.what();
}
return 0;
}Factorial of 5 is 120
Recursion vs Iteration
| Aspect | Recursion | Iteration |
|---|---|---|
| Code Readability | Often shorter and expressive | More explicit and sometimes longer |
| Memory Usage | Uses call stack: O(depth) frames (risk of overflow) | O(1) stack usage (loop variables only) |
| Performance | Function call overhead; may allocate many frames | Generally faster; no call overhead |
| Use Cases | Tree/graph traversal, divide & conquer | Simple loops, fixed iterations |
Fibonacci Sequence
#include <iostream>
int fibonacci(int n) {
if (n < 0) return 0; // simple guard
if (n <= 1) // Base cases
return n;
return fibonacci(n-1) + fibonacci(n-2);
}
int main() {
std::cout << "Fibonacci sequence:\n";
for (int i = 0; i < 10; ++i)
std::cout << fibonacci(i) << " ";
return 0;
}Fibonacci sequence: 0 1 1 2 3 5 8 13 21 34
Common Recursion Patterns
1. Divide and Conquer: Split the problem into smaller subproblems (e.g., merge sort)
2. Tree Traversal: Process nodes recursively (in-order, pre-order, post-order)
3. Backtracking: Explore possible solutions and backtrack (e.g., maze solving, N-Queens)
4. Dynamic Programming: Combine recursion with memoization to avoid redundant work
Recursion Pitfalls
- Missing base case leads to infinite recursion
- Deep recursion can cause stack overflow
- Naive solutions may repeat calculations unnecessarily
- Debugging deeply recursive code can be challenging
// Dangerous recursive function
void infiniteRecursion() {
infiniteRecursion(); // No base case!
}Tail Recursion Optimization
Tail recursion happens when the recursive call is the final action in the function.
C++ does not guarantee tail-call optimization; some compilers may optimize tail calls under certain build options. Do not rely on it for deep recursion—prefer an iterative version when stack depth matters.
// Tail-recursive factorial (may or may not be optimized by your compiler)
long long factorialTR(int n, long long acc = 1) {
if (n <= 1) return acc;
return factorialTR(n - 1, acc * n);
}Efficient Alternatives (Memoization/Iteration)
Many recursive problems have efficient non-recursive forms. For Fibonacci, an iterative approach avoids exponential blow-up and uses O(1) extra space.
#include <iostream>
long long fib_iter(int n) {
if (n <= 1) return n;
long long a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
long long c = a + b;
a = b;
b = c;
}
return b;
}
int main() {
for (int i = 0; i < 10; ++i)
std::cout << fib_iter(i) << " ";
}