C++ Recursion: Complete Guide with Examples
What is Recursion?
Recursion is when a function calls itself to solve a smaller version of the same problem. Instead of using loops to repeat work, a recursive function breaks a problem down until it reaches a simple case it can solve directly (the base case), then builds the answer back up.
Recursion is not just an academic curiosity — it is the natural way to solve problems that have recursive structure: tree traversals, directory listings, mathematical sequences, divide-and-conquer algorithms, and parsing nested data. Compilers, databases, and file systems all rely heavily on recursive algorithms.
Anatomy of a Recursive Function
Every recursive function needs two things: a base case that stops the recursion, and a recursive case that calls the function with a smaller input.
#include <iostream>
using namespace std;
void countdown(int n) {
// Base case: stop when n reaches 0
if (n <= 0) {
cout << "Liftoff!" << endl;
return;
}
// Recursive case: print and recurse with n-1
cout << n << "... ";
countdown(n - 1);
}
int main() {
countdown(5);
return 0;
}
// Output: 5... 4... 3... 2... 1... Liftoff!If you forget the base case, the function calls itself forever until the program runs out of stack memory and crashes — a stack overflow.
Factorial — The Classic Example
The factorial of n (written n!) is defined as: 0! = 1, and n! = n × (n-1)! for n > 0. This definition is inherently recursive.
#include <iostream>
using namespace std;
long long factorial(int n) {
// Base case
if (n <= 1) return 1;
// Recursive case
return n * factorial(n - 1);
}
int main() {
for (int i = 0; i <= 12; i++) {
cout << i << "! = " << factorial(i) << endl;
}
return 0;
}
// Output:
// 0! = 1
// 1! = 1
// 2! = 2
// 3! = 6
// ...
// 12! = 479001600Let us trace factorial(4):
factorial(4) = 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24Fibonacci Sequence
The Fibonacci sequence (0, 1, 1, 2, 3, 5, 8, 13, …) is defined as: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2). This maps directly to a recursive function.
#include <iostream>
using namespace std;
// Naive recursive Fibonacci — simple but SLOW
int fib(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
int main() {
for (int i = 0; i <= 10; i++) {
cout << "F(" << i << ") = " << fib(i) << endl;
}
return 0;
}
// Output: F(0)=0, F(1)=1, F(2)=1, F(3)=2, ..., F(10)=55This naive version has exponential time complexity — O(2^n). Computing fib(40) takes billions of calls because the same subproblems are computed repeatedly. The fix is memoization, covered later in this lesson.
How the Call Stack Works
Every time a function is called, the system pushes a stack frame onto the call stack. The frame holds the function’s local variables, parameters, and the return address. When the function returns, its frame is popped off.
#include <iostream>
using namespace std;
void depth(int n) {
cout << "Entering depth(" << n << ")" << endl;
if (n > 0) {
depth(n - 1);
}
cout << "Leaving depth(" << n << ")" << endl;
}
int main() {
depth(3);
return 0;
}
// Output:
// Entering depth(3)
// Entering depth(2)
// Entering depth(1)
// Entering depth(0)
// Leaving depth(0)
// Leaving depth(1)
// Leaving depth(2)
// Leaving depth(3)Notice the LIFO (last in, first out) pattern: the deepest call returns first. This is exactly how a stack data structure works.
Stack Overflow
The call stack has a finite size (typically 1-8 MB depending on the platform). If recursion goes too deep, you exhaust the stack and the program crashes.
#include <iostream>
using namespace std;
void infinite() {
static int count = 0;
count++;
if (count % 10000 == 0) {
cout << "Depth: " << count << endl;
}
infinite(); // No base case — will crash
}
// DO NOT RUN THIS — it will crash with stack overflow
// int main() { infinite(); return 0; }To avoid stack overflow: always have a base case, ensure the input shrinks toward the base case on every call, and consider iterative solutions for problems that could recurse thousands of levels deep.
Binary Search (Recursive)
Binary search divides a sorted array in half at each step — a natural fit for recursion.
#include <iostream>
#include <vector>
using namespace std;
int binary_search(const vector<int>& arr, int target, int low, int high) {
// Base case: element not found
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (arr[mid] == target) return mid; // Found
if (arr[mid] < target)
return binary_search(arr, target, mid + 1, high); // Search right
else
return binary_search(arr, target, low, mid - 1); // Search left
}
int main() {
vector<int> sorted = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
int idx = binary_search(sorted, 23, 0, sorted.size() - 1);
if (idx >= 0)
cout << "Found 23 at index " << idx << endl;
else
cout << "Not found" << endl;
cout << "Search 99: index "
<< binary_search(sorted, 99, 0, sorted.size() - 1) << endl;
return 0;
}
// Output:
// Found 23 at index 5
// Search 99: index -1String Recursion
#include <iostream>
#include <string>
using namespace std;
// Reverse a string recursively
string reverse(const string& s) {
if (s.length() <= 1) return s; // Base case
return reverse(s.substr(1)) + s[0];
}
// Check palindrome recursively
bool is_palindrome(const string& s, int left, int right) {
if (left >= right) return true; // Base case
if (s[left] != s[right]) return false;
return is_palindrome(s, left + 1, right - 1);
}
// Count occurrences of a character
int count_char(const string& s, char c, int index = 0) {
if (index >= s.length()) return 0;
int found = (s[index] == c) ? 1 : 0;
return found + count_char(s, c, index + 1);
}
int main() {
cout << reverse("hello") << endl; // olleh
string word = "racecar";
cout << word << " is "
<< (is_palindrome(word, 0, word.size()-1) ? "" : "not ")
<< "a palindrome" << endl;
cout << "Count of 'l' in hello: " << count_char("hello", 'l') << endl;
return 0;
}Power Function
Computing x^n can be done in O(log n) time using the observation that x^n = (x^(n/2))^2.
#include <iostream>
using namespace std;
// Naive: O(n)
double power_naive(double base, int exp) {
if (exp == 0) return 1;
if (exp < 0) return 1.0 / power_naive(base, -exp);
return base * power_naive(base, exp - 1);
}
// Fast: O(log n) — "exponentiation by squaring"
double power_fast(double base, int exp) {
if (exp == 0) return 1;
if (exp < 0) return 1.0 / power_fast(base, -exp);
if (exp % 2 == 0) {
double half = power_fast(base, exp / 2);
return half * half;
}
return base * power_fast(base, exp - 1);
}
int main() {
cout << "2^10 = " << power_fast(2.0, 10) << endl; // 1024
cout << "3^5 = " << power_fast(3.0, 5) << endl; // 243
cout << "2^-3 = " << power_fast(2.0, -3) << endl; // 0.125
return 0;
}Tail Recursion
A function is tail recursive if the recursive call is the very last thing the function does. Some compilers can optimize tail recursion into a loop, eliminating the stack overhead.
#include <iostream>
using namespace std;
// NOT tail recursive: multiplication happens AFTER the recursive call
long long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // Must multiply after call returns
}
// TAIL recursive: result is accumulated in a parameter
long long factorial_tail(int n, long long acc = 1) {
if (n <= 1) return acc;
return factorial_tail(n - 1, n * acc); // Nothing after this call
}
// Tail recursive sum
int sum_tail(int n, int acc = 0) {
if (n <= 0) return acc;
return sum_tail(n - 1, acc + n);
}
int main() {
cout << factorial_tail(12) << endl; // 479001600
cout << sum_tail(100) << endl; // 5050
return 0;
}Note: GCC with -O2 or higher can optimize tail calls. Clang also supports it. MSVC is less consistent. Do not rely on tail call optimization in C++ — convert to a loop if stack depth is a concern.
Recursion vs Iteration
#include <iostream>
using namespace std;
// Recursive factorial
long long fact_recursive(int n) {
if (n <= 1) return 1;
return n * fact_recursive(n - 1);
}
// Iterative factorial — generally preferred for simple cases
long long fact_iterative(int n) {
long long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
// Recursive sum of digits
int digit_sum_recursive(int n) {
if (n < 10) return n;
return (n % 10) + digit_sum_recursive(n / 10);
}
// Iterative sum of digits
int digit_sum_iterative(int n) {
int sum = 0;
while (n > 0) {
sum += n % 10;
n /= 10;
}
return sum;
}
int main() {
cout << fact_recursive(10) << endl; // 3628800
cout << fact_iterative(10) << endl; // 3628800
cout << digit_sum_recursive(12345) << endl; // 15
cout << digit_sum_iterative(12345) << endl; // 15
return 0;
}Use recursion when: the problem has recursive structure (trees, graphs, nested data), the recursive solution is dramatically simpler, and the depth is bounded (log n or small n). Use iteration when: a simple loop does the job, the recursion depth could be large, or performance is critical.
Memoization
Memoization stores the results of expensive function calls and returns the cached result when the same inputs occur again. This transforms the exponential Fibonacci into O(n).
#include <iostream>
#include <unordered_map>
using namespace std;
unordered_map<int, long long> memo;
long long fib_memo(int n) {
if (n <= 0) return 0;
if (n == 1) return 1;
// Check if already computed
if (memo.count(n)) return memo[n];
// Compute and store
memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
return memo[n];
}
int main() {
for (int i = 0; i <= 50; i++) {
cout << "F(" << i << ") = " << fib_memo(i) << endl;
}
// F(50) = 12586269025 — computed instantly!
return 0;
}Without memoization, fib(50) would take billions of operations. With memoization, it takes 50 lookups. This technique is the foundation of dynamic programming, one of the most powerful algorithmic paradigms.
Real-World Recursive Problems
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// Tower of Hanoi
void hanoi(int n, char from, char to, char aux) {
if (n == 0) return;
hanoi(n - 1, from, aux, to);
cout << "Move disk " << n << " from " << from << " to " << to << endl;
hanoi(n - 1, aux, to, from);
}
// Generate all subsets of a set
void subsets(vector<int>& set, vector<int>& current, int index) {
if (index == set.size()) {
cout << "{ ";
for (int x : current) cout << x << " ";
cout << "}" << endl;
return;
}
// Exclude element
subsets(set, current, index + 1);
// Include element
current.push_back(set[index]);
subsets(set, current, index + 1);
current.pop_back();
}
int main() {
cout << "--- Tower of Hanoi (3 disks) ---" << endl;
hanoi(3, 'A', 'C', 'B');
cout << "\n--- Subsets of {1,2,3} ---" << endl;
vector<int> set = {1, 2, 3};
vector<int> current;
subsets(set, current, 0);
return 0;
}Common Mistakes
1. Missing base case:
int bad_sum(int n) {
return n + bad_sum(n - 1); // Never stops → stack overflow
}
// Fix: add base case
int good_sum(int n) {
if (n <= 0) return 0;
return n + good_sum(n - 1);
}2. Input not converging to base case:
int oops(int n) {
if (n == 0) return 0;
return oops(n + 1); // Going AWAY from 0 → infinite recursion
}3. Excessive copying in parameters:
// BAD: copies the vector at every level
void explore(vector<int> path) { /* ... */ }
// GOOD: pass by reference, backtrack
void explore(vector<int>& path) { /* ... path.pop_back(); */ }Practice Exercises
Exercise 1: Write a recursive function to compute the sum of digits of a number.
Exercise 2: Write a recursive function that prints all permutations of a string.
Exercise 3: Implement a recursive merge sort on a vector<int>.
Exercise 4: Write a recursive function to flatten a nested vector (e.g., vector<vector<int>> into vector<int>).
Exercise 5: Implement the memoized Fibonacci using std::array instead of unordered_map for better cache performance.
Summary
Recursion is a fundamental programming technique where a function solves a problem by calling itself with smaller inputs. You learned how to write base cases, trace the call stack, avoid stack overflow, implement classic algorithms like factorial, Fibonacci, and binary search, and use memoization to tame exponential blowup. The key insight: recursion is most powerful when the problem itself has recursive structure. For linear problems, prefer iteration. In the next lesson, you will move on to loops — for, while, and do-while — to master the other half of control flow.
