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 two parts. There is a base case that returns without recursing, and there is a recursive call that moves towards the base case. Whether recursion is the right tool depends entirely on the shape of the problem.
The previous lesson in this module covered "How Do Default Arguments and Overloading Coexist?", and the next lesson in this module is about "How Do Headers and Multiple Files Organize a Program?".
The two parts of every recursive function
A recursive function is defined in terms of itself. It needs a base case, which gives back a result without recursing, and a recursive case, which calls the function with a smaller input.
#include <iostream>
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 that is missing a base case runs until the stack overflows.
What the call stack does
Each call to a function creates a stack frame that holds 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 <iostream>
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 of 5 runs, it calls factorial of 4, which calls factorial of 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 <iostream>
#include <string>
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. You find the next word, you count it, and you 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 the stack depth.
#include <iostream>
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 is this. Use recursion when the problem is defined recursively, such as trees, graphs, nested structures and divide and conquer. 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 one is to make the recursive call the last thing that the function does, so that the compiler can turn it into a loop. The second one is to express the recursion with an explicit accumulator parameter, which turns tail recursion into a loop by construction.
#include <iostream>
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 in the wrong direction.
- A recursive case that does not shrink. If the argument grows, then 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, and the frames unwind when the base case returns.
- Use recursion for nested data structures, such as trees, folders, expressions and linked lists.
- Use a loop for flat sequences, because 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, and then rewrite it as a loop and compare them. 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.