Recursion
GOALWrite a function that calls itself, and stop it at the right moment.
A function is allowed to call itself. That turns a big job into the same job on something smaller, until you reach a case so easy you can answer it outright. Write that stopping case FIRST — forget it and the program never ends.
ON THIS PAGE
//THE EXAMPLE
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n - 1);
}
int main() {
cout << factorial(5) << endl;
return 0;
}120
//LINE BY LINE
Watch it run
factorial(5) is called, and goes onto the call stack.
Where the calls are kept
When a function calls itself the older call does not vanish — it waits. The computer stacks them up: the one that started last finishes first.
How factorial(3) unfolds, then folds back up
factorial(3)
factorial(2)
factorial(1) -> 1
2 * 1 -> 2
6As soon as the deepest call answers, the multiplications waiting above it happen one by one. That is why recursion is described as going down and then coming back up.
Too many layers and this stack fills up. C++ crashes; Python raises RecursionError, by default after about 1000 calls.
Recursion or a loop?
Anything you can write with recursion you can also write with a loop. The choice is about which one READS more clearly.
| Problem | Which fits |
|---|---|
| 1-ээс n хүртэл нэмэх / Add 1 to n | Давталт / A loop |
| Массиваас хамгийн их утгыг олох / Largest in an array | Давталт / A loop |
| Модны мөчрүүдийг тойрох / Walking a tree | Рекурс / Recursion |
| Бүх боломжийг туршиж үзэх / Trying every possibility | Рекурс / Recursion |
A rule of thumb: if the problem contains a smaller copy of itself, reach for recursion. If it is a sequence of steps, reach for a loop.