Some problems are made of smaller copies of themselves. A folder contains files and other folders, which contain more files and folders. To reverse a word, reverse everything after the first letter and put the first letter on the end. To search a sorted list, look at the middle, then search half of the list in exactly the same way.
A recursive function solves problems like these by calling itself on a smaller piece of the problem, until the piece is so small the answer is obvious. It sounds like a trick, but it's one of the most powerful ideas in programming, and it appears in sorting algorithms, games, compilers and file systems.
In this lesson you'll write recursive functions step by step, understand exactly what happens on the call stack when they run, avoid the infinite recursion that crashes programs, make slow recursion fast with memoization, and learn when a simple loop is the better choice.
Base case and recursive case
Every recursive function needs two parts:
- A base case: a situation simple enough to answer directly, without another call.
- A recursive case: the function calls itself with a smaller problem that moves towards the base case.
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}factorial(4) asks for 4 * factorial(3), which asks for 3 * factorial(2), then 2 * factorial(1). factorial(1) is the base case and returns 1, and the answers multiply back up: 2, 6, 24.
The call stack
Each time a function is called, C++ creates a stack frame holding its parameters and local variables, and puts it on top of the call stack. When the function returns, its frame is removed and control goes back to the frame below.
With recursion, frames pile up: factorial(4) waits for factorial(3), which waits for factorial(2), and so on. Only when the base case returns do the frames finish, one by one, from the top. This is why each call can have its own n without them interfering.
The stack has a limited size, often 1 to 8 MB. Recursion that goes too deep, or never reaches a base case, fills it and crashes the program with a stack overflow.
Recursion with vectors and strings
Recursion often works on part of a collection, passing an index or a range rather than copying data:
int sum(const vector<int>& v, size_t i) {
if (i == v.size()) return 0; // nothing left
return v[i] + sum(v, i + 1); // this item plus the rest
}Passing the vector by const& avoids copying it at every level. Binary search is a classic: look at the middle of a sorted range; if it's not the target, search only the left half or only the right half. Each call halves the problem, so even a million items need only about 20 calls.
Recursion or a loop?
Anything recursive can be written with a loop, and vice versa. Choose whichever is clearer:
| Recursion fits | A loop fits |
|---|---|
| Tree shapes: folders, menus, family trees | Counting and simple repetition |
| Divide and conquer: binary search, merge sort | Processing items one after another |
| Trying choices: puzzles, mazes | Very deep problems (millions of levels) |
Some recursive functions repeat work. A naive fib(n) = fib(n - 1) + fib(n - 2) recalculates the same values billions of times for fib(50). Memoization, storing answers you've already computed, fixes that.
C++ Recursion Syntax
Recursion pattern
ReturnType solve(Problem p) {
if (/* p is simple */) {
return /* direct answer */; // base case
}
return /* combine */ solve(/* smaller p */); // recursive case
}C++ Recursion Summary
- A recursive function calls itself on a smaller version of the problem.
- Every recursive function needs a base case that returns without recursing.
- Each call gets its own stack frame; too many frames cause a stack overflow.
- Pass large data by const reference and use indexes or ranges to shrink the problem.
- Use memoization to avoid repeated work, and loops for simple or very deep repetition.
C++ Recursion Examples
Each example shows the code, the output it produces and what each part does.
Factorial and sum of digits
#include <iostream>
using namespace std;
long long factorial(int n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
int digitSum(int n) {
if (n < 10) return n;
return n % 10 + digitSum(n / 10);
}
int main() {
cout << "5! = " << factorial(5) << endl;
cout << "20! = " << factorial(20) << endl;
cout << "Digit sum of 4096: " << digitSum(4096) << endl;
return 0;
}5! = 120
20! = 2432902008176640000
Digit sum of 4096: 19Line-by-line explanation
- Line 4long long, because factorials grow very fast. 20! is the largest that fits.
- Line 5The base case: 0! and 1! are both 1.
- Line 10A single digit is its own sum.
- Line 11The last digit plus the digit sum of the rest: 6 + digitSum(409), and so on.
Watching the call stack
#include <iostream>
#include <string>
using namespace std;
int countdown(int n, int depth) {
string indent(depth * 2, ' ');
cout << indent << "countdown(" << n << ")" << endl;
if (n == 0) {
cout << indent << "liftoff, returning 0" << endl;
return 0;
}
int result = 1 + countdown(n - 1, depth + 1);
cout << indent << "returning " << result << endl;
return result;
}
int main() {
countdown(3, 0);
return 0;
}countdown(3)
countdown(2)
countdown(1)
countdown(0)
liftoff, returning 0
returning 1
returning 2
returning 3Line-by-line explanation
- Line 6Indent by two spaces per level, so you can see how deep each call is.
- Lines 8 to 11The base case stops the recursion.
- Line 12This call waits here until the smaller call returns.
- Line 13These lines print on the way back up, in reverse order.
Recursive binary search
#include <iostream>
#include <vector>
using namespace std;
int findIndex(const vector<int>& v, int target, int low, int high) {
if (low > high) return -1;
int mid = low + (high - low) / 2;
if (v[mid] == target) return mid;
if (v[mid] < target) return findIndex(v, target, mid + 1, high);
return findIndex(v, target, low, mid - 1);
}
int main() {
vector<int> scores = {3, 8, 15, 21, 34, 42, 57, 66, 80};
cout << "34 is at index " << findIndex(scores, 34, 0, scores.size() - 1) << endl;
cout << "80 is at index " << findIndex(scores, 80, 0, scores.size() - 1) << endl;
cout << "50 is at index " << findIndex(scores, 50, 0, scores.size() - 1) << endl;
return 0;
}34 is at index 4
80 is at index 8
50 is at index -1Line-by-line explanation
- Line 6An empty range means the target isn't there.
- Line 7low + (high - low) / 2 finds the middle without risking overflow.
- Lines 9 to 10Search only the half that could contain the target.
- Line 14Binary search only works on sorted data.
Common C++ Recursion Mistakes
No base case
int countDown(int n) {
cout << n << endl;
return countDown(n - 1); // never stops: stack overflow
}int countDown(int n) {
if (n < 0) return 0;
cout << n << endl;
return countDown(n - 1);
}Copying a big vector at every level
int sum(vector<int> v, size_t i); // copies v on every callint sum(const vector<int>& v, size_t i); // shares one vectorNaive recursion that repeats work
long long fib(int n) {
if (n < 2) return n;
return fib(n - 1) + fib(n - 2); // fib(50) takes minutes
}long long fib(int n, vector<long long>& memo) {
if (n < 2) return n;
if (memo[n] != 0) return memo[n];
return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}C++ Recursion in Real Projects
Recursion in practice
File managers calculate folder sizes recursively, compilers read nested code such as brackets inside brackets with recursive functions, and games use recursion to search possible moves in chess and puzzles. Fast sorting algorithms such as quicksort and merge sort, including the one inside std::sort, are built on divide-and-conquer recursion.
C++ Recursion FAQ
Is recursion slower than a loop in C++?
Usually a little, because every call has to set up a new stack frame and return from it. When optimising, g++ and clang can turn some recursive functions into loops, particularly when the recursive call is the very last thing the function does (a tail call), but the C++ standard doesn't guarantee this. For simple counting or summing, a loop is both faster and safer.
Why does my recursive function return the wrong value?
A common cause is calling the function without returning its result, as in if (v[i] != x) find(v, x, i + 1);. The recursive call does the work, but its answer is thrown away and the outer call falls off the end of the function, which is undefined behaviour. Write return find(v, x, i + 1);. g++ warns with "control reaches end of non-void function".
Can two functions call each other recursively?
Yes, this is called mutual recursion. For example, isEven(n) can call isOdd(n - 1) and isOdd can call isEven, both stopping at 0. Because each function uses the other, declare one of them with a prototype above both definitions so the compiler knows it exists.
How do I turn a recursive function into a loop?
For simple recursion such as factorial, keep a running result in a variable and loop down from n instead of calling yourself. For recursion that branches, such as walking through folders or a tree, store the work still to do in your own vector used as a stack: push the starting item, then loop while the stack isn't empty, popping one item and pushing its children. This avoids stack overflow on very deep data.
Can main call itself in C++?
No. The C++ standard forbids calling main from inside your program, even though g++ compiles it without complaint unless you add -pedantic. If you want a program to start over, put the work in a separate function and call that from a loop in main.
C++ Recursion Exercises
Answer each one and check it instantly. If you get stuck, open the hint before the answer.
Complete the base case so the function stops at zero.
int sumTo(int n) {
if (n == ) return 0;
return n + sumTo(n - 1);
}Using the lesson's factorial function, what does factorial(4) return?
What does this print?
int f(int n) {
if (n == 0) return 0;
return 2 + f(n - 1);
}
cout << f(5) << endl;What happens when recursion never reaches a base case?
Why is naive recursive Fibonacci slow?
C++ Recursion Quiz
5 questions to check what you learned.
What is a recursive function?
- A function that calls itself
- A function with a loop
- A function with no return value
- A function inside a class
What is the base case?
- The first line of main
- The largest input
- The default parameter
- The simplest input, answered directly without another recursive call
How many calls does binary search need for about a million sorted items?
- About a million
- About 1,000
- About 20
- Exactly 2
What does each recursive call get on the call stack?
- Nothing
- Its own frame with its own parameters and local variables
- A shared copy of every variable
- A new thread
When is a loop usually better than recursion?
- Simple repetition that could go millions of levels deep
- Walking a folder tree
- Binary search
- Solving a maze