Recursion
When a function calls itself to solve a smaller version of the same problem
- explain what a recursive function is,
- tell the base case apart from the recursive case,
- follow how the call stack grows and then unwinds,
- read classic examples like factorial and Fibonacci,
- decide when recursion is clearer than a loop.
1. What is recursion?
Think of a set of nesting dolls (matryoshka). You open the big doll and find a smaller one inside. You open that one and find an even smaller one. You keep going until you reach the tiniest doll that does not open at all. That last little doll is where you stop.
Recursion works the same way. A recursive function keeps calling itself on a smaller piece of the problem. It must have a moment where it stops calling itself, just like the smallest doll that will not open. Without that stopping point, it would go on forever.
In the Functions in C++ topic you learned that a function can call another function. Here is the surprising part: a function is allowed to call itself. That is all recursion really is.
2. Base case vs. recursive case
Every good recursive function has exactly two parts:
- The base case is the simplest problem, the one you can answer right away without calling yourself again. It is the smallest doll. It stops the recursion.
- The recursive case is where the function calls itself on a smaller problem and uses that answer to build its own.
Look at counting down from a number to zero:
#include <iostream>
using namespace std;
void countdown(int n) {
if (n < 0) { // BASE CASE: nothing left to do
return;
}
cout << n << " "; // do a little work
countdown(n - 1); // RECURSIVE CASE: smaller problem
}
int main() {
countdown(3);
return 0;
}Expected output:
3 2 1 0 Notice how each call passes n - 1. The number keeps shrinking: 3, then 2, then 1, then 0, then -1. When it finally reaches -1 the base case runs return; and the chain of calls stops.