JavaScript, lesson 11
A recursive function is one that calls itself. That sounds like a loop that never ends, but it works because each call handles a smaller version of the problem, and one very small version is answered directly. Recursion is the natural fit for data that contains smaller data of the same shape: folders inside folders, comments with replies, arrays nested inside arrays.
Every recursive function needs:
Follow it by hand: sumTo(4) is 4 + sumTo(3), which is 4 + 3 + sumTo(2), and so on until
sumTo(0) returns 0. Then the waiting additions finish one by one: , , , , .
2 exercises to try what you just read.
013610Each call that has not finished yet waits on the call stack, with its own copy of its
parameters and local variables. That is why n can be 4 in one call and 3 in another at the
same time. The stack has a limit; in Node.js it allows roughly ten thousand nested calls,
depending on how much each call stores. Go past it and you get
RangeError: Maximum call stack size exceeded. Forgetting the base case, or a recursive call
that does not get smaller, leads straight there.
For a simple count like sumTo, a loop is better. Recursion shines when the shape of the data
branches.
Here is a function that counts every number in an array whose elements may themselves be arrays, to any depth:
You do not need to picture every level. Trust that the recursive call correctly handles a smaller piece (the leap of faith), and only check that the base case is right and that combining the pieces is right.
Some problems split into several smaller problems. Generating all strings of n coin flips
splits into "those starting with H" and "those starting with T":
Branching recursion can be slow when the same subproblem is solved again and again (naive
Fibonacci is the classic example). Storing answers you have already computed in a Map fixes
that; this trick is called memoization.
Recursive problems such as factorials produce huge numbers quickly. Regular numbers stay
exact only up to Number.MAX_SAFE_INTEGER (about 9 quadrillion). For larger whole numbers use
BigInt: write literals with an n suffix (20n) or convert with BigInt(x). You cannot mix
BigInt and regular numbers in arithmetic without converting one of them.
A gift is described as a JSON array. Numbers are the values of gifts; arrays are boxes that can contain gifts and other boxes. Write recursive code to print two lines:
total N: the sum of all numbers at every depth;depth D: the deepest nesting level, where the outer array is level 1 and an empty array
still counts as a level.The input is one line of JSON.
Sample input:
Sample output:
You climb a staircase of N steps, taking either 1 or 2 steps at a time. How many different
ways are there to reach the top? For 3 steps there are 3 ways: 1+1+1, 1+2 and 2+1.
Write a recursive function ways(n): there is 1 way to climb 0 steps (do nothing) and 1 way to
climb 1 step; for more steps, the first move is either 1 step (leaving n - 1) or 2 steps
(leaving n - 2). Use a Map to remember results you have already computed, otherwise large
inputs will be far too slow. Return a BigInt so that the answer stays exact.
The input is one whole number N with 0 <= N <= 300. Print the number of ways.
Sample input:
Sample output:
function sumTo(n) {
if (n === 0) return 0; // base case
return n + sumTo(n - 1); // recursive case: a smaller problem
}
console.log(sumTo(4)); // 10function countNumbers(value) {
if (!Array.isArray(value)) {
return typeof value === "number" ? 1 : 0; // base case: a single value
}
let count = 0;
for (const item of value) {
count += countNumbers(item); // recurse into each element
}
return count;
}
console.log(countNumbers([1, [2, 3, [4]], "x", [[5]]])); // 5function flips(n) {
if (n === 0) return [""];
const shorter = flips(n - 1);
return [...shorter.map((s) => "H" + s), ...shorter.map((s) => "T" + s)];
}
console.log(flips(2)); // [ 'HH', 'HT', 'TH', 'TT' ][5, [10, [1, 2]], []]total 18
depth 333