← Data structures from scratch · Lesson 15/32
A function that calls itself
Solve one piece and hand off the rest
A recursive function calls itself with a smaller problem. To finish, it needs two things:
- A base case: a problem so small it's answered without calling itself again.
- A recursive step that gets closer to the base case on every call.
The countdown below prints n and asks another copy of itself to continue from n - 1. When it reaches 0, it stops.
$ node leccion.js
Press RUN (or Ctrl+Enter).
What to look at
3, 2, 1 and liftoff: four calls, and the last one is the one that doesn't call itself again.
The whole lesson on one page
Solve one piece and hand off the rest
A recursive function calls itself with a smaller problem. To finish, it needs two things:
- A base case: a problem so small it's answered without calling itself again.
- A recursive step that gets closer to the base case on every call.
The countdown below prints n and asks another copy of itself to continue from n - 1. When it reaches 0, it stops.
function cuentaRegresiva(n) {
if (n === 0) { // base case
console.log("liftoff!");
return;
}
console.log(n);
cuentaRegresiva(n - 1); // a smaller problem
}
cuentaRegresiva(3);
3, 2, 1 and liftoff: four calls, and the last one is the one that doesn't call itself again.
The call stack
Every call that hasn't finished waits on the call stack, a real stack (like the one from the previous unit): the last one in is the first to finish. factorial(3) can't answer until factorial(2) answers, and that one waits for factorial(1).
When the one on top reaches the base case, the answers come back down one by one and each call finishes its multiplication. The program prints with indentation on the way in and out so you can watch the stack grow and empty.
function factorial(n, sangria = "") {
console.log(sangria + "in factorial(" + n + ")");
let r;
if (n <= 1) r = 1; // base case
else r = n * factorial(n - 1, sangria + " "); // waits for the answer
console.log(sangria + "out factorial(" + n + ") = " + r);
return r;
}
factorial(3);
The three go in as 3, 2, 1 and come out reversed, 1, 2, 3: that's a stack. factorial(1) is the only one that answers on its own; the others multiply what they get back.
No base case, it overflows
If the function never reaches a base case, the stack grows until the language says enough. In JavaScript that's a RangeError: a stack overflow. It happens when the base case is forgotten, and also with one the recursive step never reaches, like stepping down by 2 hoping to hit 1 from an even number.
For the same reason, even when it's well written, a recursion hundreds of thousands of levels deep can overflow: that's when a loop is better.
function sinFin(n) {
return sinFin(n + 1); // never stops
}
function deDosEnDos(n) {
if (n === 1) return "made it";
return deDosEnDos(n - 2); // from an even number, it skips 1
}
for (const prueba of [() => sinFin(0), () => deDosEnDos(7), () => deDosEnDos(8)]) {
try {
console.log(prueba());
} catch (e) {
console.log(e.name + ": " + e.message);
}
}
The first and third blow up with RangeError. From 7 you do reach 1; from 8 it overshoots (8, 6, 4, 2, 0, −2…) and never stops.
Fibonacci: when recursion repeats work
Each Fibonacci number is the sum of the two before it: 1, 1, 2, 3, 5, 8… Written as is, fib(n) calls fib(n - 1) and fib(n - 2), and each of those splits in two again. The same fib(3) gets computed thousands of times and the calls grow like O(2ⁿ).
The cure is memoizing: store what's already computed in a Map and return it instead of recomputing. Then each fib(k) is computed only once: O(n). It's the same problem as "how many ways can you climb stairs 1 or 2 steps at a time?", the challenge below.
let llamadas = 0;
function fib(n) {
llamadas++;
if (n <= 2) return 1;
return fib(n - 1) + fib(n - 2);
}
let llamadasMemo = 0;
const memo = new Map();
function fibMemo(n) {
llamadasMemo++;
if (n <= 2) return 1;
if (memo.has(n)) return memo.get(n); // already knew it
const r = fibMemo(n - 1) + fibMemo(n - 2);
memo.set(n, r);
return r;
}
for (const n of [10, 20, 25]) {
llamadas = 0;
const r = fib(n);
console.log("fib(" + n + ") =", r, "with", llamadas, "calls");
}
console.log("memoized, fib(25) =", fibMemo(25), "with", llamadasMemo, "calls");
From fib(10) to fib(25) the calls go from 109 to 150,049. Memoized, the same fib(25) takes 47 calls.