Chapter 3 · Data
Recursion
Step 1 of 20 · Concept
A function can call itself
By the end of this lesson you write functions that call themselves, and read the error when they never stop.
function countdown(n) {
if (n === 0) {
console.log("Go!");
return;
}
console.log(n);
countdown(n - 1);
}
countdown calls itself with a smaller n. That is recursion. The base case, n === 0, does not call
again, so the calls stop.
Step 2 of 20 · Quiz
Predict the countdown
Type the missing line.
function countdown(n) {
if (n === 0) {
console.log("Go!");
return;
}
console.log(n);
countdown(n - 1);
}
countdown(2);
Step 3 of 20 · Demo
See it run
Run it and compare with your answer. Then change the last line to countdown(5); and run it again.
Step 4 of 20 · Concept
Each call waits for the next
The factorial of 3 is 3 * 2 * 1. Each call does one multiplication:
function fact(n) {
if (n <= 1) {
return 1;
}
return n * fact(n - 1);
}
console.log(fact(3));
| call | waits for | then returns |
|---|---|---|
fact(3) | fact(2) | 3 * 2, which is 6 |
fact(2) | fact(1) | 2 * 1, which is 2 |
fact(1) | nothing: the base case | 1 |
Each call has its own frame with its own n (lesson 7). The frames pile up, then return in reverse.
Step 5 of 20 · Trace
Watch the frames pile up
Press Next to run one call or one return at a time. The rows fact(1), fact(2) and fact(3) show the value
that came back.
function fact(n) {
if (n <= 1) {
return 1;
}
return n * fact(n - 1);
}
console.log(fact(3));- Only the module's frame. Line 7 calls
fact(3). - A frame for
factwithn3. 3 is not<= 1, so line 5 callsfact(2). - A second
factframe,n2, callsfact(1). The first one waits. - A third frame,
n1: the base case. Line 3 returns 1. - That frame is gone. The
n2 frame got 1 back and returns2 * 1. - The
n3 frame got 2 back and returns3 * 2. - Only the module's frame is left:
fact(3)gave 6. Line 7 logs it. 6is printed. The program is finished.
Step 6 of 20 · Quiz
How many frames at once?
While fact(3) runs, what is the most fact frames on the stack at one time?
function fact(n) {
if (n <= 1) {
return 1;
}
return n * fact(n - 1);
}
console.log(fact(3));Step 7 of 20 · Exercise
Your turn: sum of digits
Write sumDigits(n), the sum of the digits of n:
- A number below 10 has one digit: its sum is
nitself. - Else: the last digit,
n % 10, plussumDigitsof the rest,Math.floor(n / 10).
The program must print:
10
7
Write the base case first: a one-digit number. Without it, the rest of 7 is 0, and sumDigits(0) calls sumDigits(0) without end, until Node stops with a RangeError. The next part of this lesson reads it.
An if (n < 10) that returns n. After it, return the last digit plus the call on the rest.
return (n % 10) + sumDigits(Math.floor(n / 10));
Step 8 of 20 · Concept
No base case, no end
Without a base case, every call makes one more frame. The stack has room for about 10,000 such frames. Then Node
stops with RangeError: Maximum call stack size exceeded.
Read it as in lesson 5. Node prints ten at lines, all down: the newest call first, at main.js:2:3, then nine
at main.js:2:10.
Step 9 of 20 · Demo
A countdown that never stops
down has no base case. Run it: Start, then the RangeError.
Step 10 of 20 · Quiz
Where is the fix?
This program stops with the message after it. What fixes it?
function down(n) {
return down(n + 1);
}
console.log("Start");
down(0);
Start
main.js:2
return down(n + 1);
^
RangeError: Maximum call stack size exceeded
at down (main.js:2:3)
at down (main.js:2:10)
at down (main.js:2:10)
...
function down(n) {
return down(n + 1);
}
console.log("Start");
down(0);Start
main.js:2
return down(n + 1);
^
RangeError: Maximum call stack size exceeded
at down (main.js:2:3)
at down (main.js:2:10)
at down (main.js:2:10)
...Step 11 of 20 · Try it
Try it: give it a base case
sumTo(5) should add 5 + 4 + 3 + 2 + 1. Run it: a RangeError, and nothing is logged.
Add if (n === 0) { return 0; } as the first line of sumTo. Then it prints 15.
sumTo(0) must give 0 without calling sumTo(-1). Put the if before the return that calls.
Step 12 of 20 · Concept
Two calls each time
function fib(n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
Each fibonacci number is the sum of the two before it. fib calls itself twice, so the calls branch and repeat work:
fib(10) makes 177 calls.
Step 13 of 20 · Demo
Recursion and a loop agree
fibLoop keeps the last two numbers in a and b. calls counts the calls of fib. Run it.
Then change both 10s to 25: the loop takes 25 rounds, while fib makes 242,785 calls.
Step 14 of 20 · Concept
Arrays inside arrays, any depth
Array.isArray(x) is true when x is an array. To add up all the numbers, at any depth:
- a number: add it;
- an array: call yourself on it, and add what that call returns.
An array of numbers only makes no more calls: that is the base case.
Step 15 of 20 · Quiz
What is the sum?
What does this program log?
function sumAll(xs) {
let total = 0;
for (const x of xs) {
if (Array.isArray(x)) {
total += sumAll(x);
} else {
total += x;
}
}
return total;
}
console.log(sumAll([1, [2, 3], [4, [5]]]));
Step 16 of 20 · Demo
See it run
Run it and compare with your answer. Then add [6, [7]] to the array and run it again.
Step 17 of 20 · Exercise
Your turn: flatten it
Write flatten(xs): one flat array of all the numbers, at any depth.
- For a number, push it.
- For an array, flatten it, then push each of its items.
The program must print:
1, 2, 3, 4, 5
flat.push(flatten(x)) pushes the whole array as one item, so the arrays stay nested: 1, 2,3, 4,5. Push its items, one by one.
A for...of over xs with Array.isArray(x), as sumAll does. ... hands an array's items over one by one, as with Math.max (lesson 12).
flat.push(...flatten(x));
Step 18 of 20 · Check yourself
Check yourself: palindromes
A palindrome reads the same both ways. Write isPalindrome(word):
- A word of 0 or 1 letters is one.
- Else its first and last letters match, and its middle,
word.slice(1, -1), is one.
The output must be:
level true
lever false
The base case first, then one return that joins two questions with &&: do the ends match, and is the middle a palindrome?
Step 19 of 20 · Challenge · optional
Challenge: a fast fibonacci
Optional.
Run it: fib(50) would take billions of calls, so it does not finish by itself. Press Stop.
Make it fast: remember each answer in a Map, a memo, and look there first. The program must print:
12586269025
Every call must share one Map: only the first call leaves memo out, so only it makes a new one with the default memo = new Map(). A memo not passed down never finishes either: press Stop.
Pass memo down to both inner calls. Before working, ask memo.has(n); after, memo.set(n, value).
function fib(n, memo = new Map()) {
Step 20 of 20 · Recap
Recap
- A recursive function calls itself; its base case stops the calls.
- Each call has its own frame: they pile up, then return in reverse.
- No base case:
RangeError: Maximum call stack size exceeded, after about 10,000 frames. Array.isArray(x)lets one function walk arrays inside arrays.
Next: lesson 15 keeps a function's variables alive after it returns: closures.
Review
4 questions from this lesson, in a new order each time. Answer from memory: 3 of 4 right on the first try passes. On a day after you finish the lesson, a pass earns 15 XP.
The review needs JavaScript.
function countdown(n) {
if (n === 0) {
console.log("Go!");
return;
}
console.log(n);
countdown(n - 1);
}
countdown(2);
function sumDigits(n) {
// 1. below 10: the sum is n itself
// 2. else: last digit + sumDigits of the rest
}
console.log(sumDigits(1234));
console.log(sumDigits(7));
function down(n) {
return down(n + 1);
}
console.log("Start");
down(0);
function sumTo(n) {
return n + sumTo(n - 1);
}
console.log(sumTo(5));
let calls = 0;
function fib(n) {
calls++;
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
function fibLoop(n) {
let a = 0;
let b = 1;
for (let i = 0; i < n; i++) {
[a, b] = [b, a + b];
}
return a;
}
console.log(fib(10), fibLoop(10));
console.log("calls:", calls);
function sumAll(xs) {
let total = 0;
for (const x of xs) {
if (Array.isArray(x)) {
total += sumAll(x);
} else {
total += x;
}
}
return total;
}
console.log(sumAll([1, [2, 3], [4, [5]]]));
function flatten(xs) {
const flat = [];
// 1. a number: push it
// 2. an array: flatten it, push its items
return flat;
}
console.log(flatten([1, [2, 3], [4, [5]]]).join(", "));
// isPalindrome(word): true when the word reads
// the same both ways
console.log("level", isPalindrome("level"));
console.log("lever", isPalindrome("lever"));
function fib(n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
console.log(fib(50));