Recursion in C++ works by having a function call itself with a smaller version of the same problem, until it reaches a base case that stops the chain. Every recursive function needs those two parts: a base case that returns without recursing, and a recursive call that moves towards the base case. Whether recursion is the right tool depends entirely on the shape of the problem.
The two parts of every recursive function
A recursive function is defined in terms of itself. It needs a base case, which returns a result without recursing, and a recursive case, which calls the function with a smaller input.
#include
int count_down(int n) {
if (n <= 0) { // base case
return 0;
}
std::cout << n << ' ';
return count_down(n - 1) + 1; // recursive case
}
int main() {
std::cout << '\n';
std::cout << "steps: " << count_down(5) << '\n';
return 0;
}The base case stops the recursion, and the recursive case always moves one step closer to it. A recursive function missing a base case runs until the stack overflows.
What the call stack does
Each call to a function creates a stack frame holding its parameters, its local variables and the place to return to. A recursive function creates a new frame every time it calls itself, and those frames pile up until the base case returns and they unwind one by one.
#include
long long factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
int main() {
for (int i = 0; i <= 10; ++i) {
std::cout << i << "! = " << factorial(i) << '\n';
}
return 0;
}The output is the familiar series:
0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800When factorial(5) runs, it calls factorial(4), which calls factorial(3), and so on. Each frame holds its own n, so the multiplication happens on the way back up.
Recursion over collections
Recursion shines when the data is itself nested. A tree, a folder, a linked list or a parsed expression all have a recursive shape, and the code that walks them is naturally recursive too.
#include
#include
int count_words(const std::string& text) {
std::string::size_type start = text.find_first_not_of(' ');
if (start == std::string::npos) {
return 0; // no words left
}
std::string::size_type end = text.find(' ', start);
if (end == std::string::npos) {
end = text.size();
}
return 1 + count_words(text.substr(end));
}
int main() {
std::cout << "words: " << count_words("fresh bread every morning") << '\n';
return 0;
}This is a simple recursive descent: find the next word, count it, and recurse on the remainder. A loop would work here too, but the recursive version maps directly onto the definition of "a list of words".
When recursion is the wrong answer
For a flat sequence, a loop is usually better: it uses less memory, it is easier to follow, and it is not limited by stack depth.
#include
int sum_loop(const int values[], int count) {
int total = 0;
for (int i = 0; i < count; ++i) {
total += values[i];
}
return total;
}
int sum_recursive(const int values[], int count) {
if (count == 0) {
return 0;
}
return values[0] + sum_recursive(values + 1, count - 1);
}
int main() {
int values[5] = {3, 7, 2, 9, 4};
std::cout << "loop: " << sum_loop(values, 5) << '\n';
std::cout << "recursive: " << sum_recursive(values, 5) << '\n';
return 0;
}Both produce the same answer, but the loop version keeps a single frame alive while the recursive version creates one frame per element.
The practical rule: use recursion when the problem is defined recursively — trees, graphs, nested structures, divide and conquer — and use a loop when you are simply walking a flat sequence.
Tail recursion and the stack
Deep recursion can exhaust the stack. A million elements means a million stack frames, and most systems will run out before you finish. Two habits help.
The first is to make the recursive call the last thing the function does, so the compiler can turn it into a loop. The second is to express the recursion with an explicit accumulator parameter, which turns tail recursion into a loop by construction.
#include
long long sum_to(int n, long long accumulator = 0) {
if (n == 0) {
return accumulator;
}
return sum_to(n - 1, accumulator + n);
}
int main() {
std::cout << "sum to 1000: " << sum_to(1000) << '\n';
return 0;
}This version has one frame per call in the worst case too, but the compiler is able to optimise the tail call into a jump, so it runs in constant stack space.
Common mistakes
- No base case, or a base case that is never reached because the argument moves the wrong way.
- A recursive case that does not shrink. If the argument grows, the recursion never ends.
- Forgetting to return the recursive result. A function that computes the answer but forgets to hand it back returns garbage.
- Deep recursion on a large input. A loop or an explicit stack is safer.
Quick reference
- Every recursive function needs a base case and a recursive case that approaches it.
- Each call consumes a stack frame; the frames unwind when the base case returns.
- Use recursion for nested data structures — trees, folders, expressions, linked lists.
- Use a loop for flat sequences; it is cheaper and easier to read.
- Keep the recursive call in tail position when you can, or pass an accumulator.
- A base case that is unreachable is the same as having no base case at all.
Try it yourself: write a recursive function that reverses the characters of a string, then rewrite it as a loop and compare. Next, write a recursive function that sums the digits of a number, and check that it stops at zero rather than at a negative number. Finally, write a recursive function for the greatest common divisor and compare its step count with the iterative version for the numbers 1071 and 462.