SyntaxPilot
Courses/JavaScript Coding Questions/Lesson 24
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

JavaScript Coding Questions · Lesson 24 of 30

Recursion questions

sum of digits and power recursivelyall permutations of a stringall subsets; call stack depth (RangeError: Maximum call stack size exceeded)

These are the notes for JavaScript Coding Questions, episode 24, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Last episode we predicted event loop output. Today: recursion, a function that calls itself. Three questions interviewers love: sum of digits and power written recursively, all permutations of a string, and all subsets of a list. On the way we meet the error every beginner sees, RangeError: Maximum call stack size exceeded, for two different reasons, and we fix both.

Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.

Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. When a program crashes, we show the real first lines of the error, up to the RangeError line; after that Node prints about ten lines starting with at (where each waiting call was) and its version, which we cut.

First: recursion in one minute

You're in a dark cinema and want to know your row number. You can't see. So you ask the person in front: "which row are you in?" Your row is their row + 1. They don't know either, so they ask the person in front of them, and so on. The person in row 1 has nobody in front, so they just know: "row 1". Then the answers travel back: 2, 3, 4…, each person adding 1, until the answer reaches you.

  • Recursion: a function that calls itself on a smaller version of the same problem.
  • Base case: the case small enough to answer without calling again (row 1). Without it, the calls never stop.
  • Recursive case: the step that calls the function again on a smaller input (row(front) + 1).
  • Call stack: the list of calls that have started but not finished. Each waiting call is a stack frame (its own copy of the parameters and local variables). A new call goes on top; when it returns, it is removed.
  • Unwinding: when the base case returns, the waiting calls finish one by one, from the top of the stack down to the first call.
function row(peopleInFront, depth = 0) {
  const pad = "  ".repeat(depth);
  if (peopleInFront === 0) {
    console.log(pad + "nobody in front: I'm in row 1");
    return 1;
  }
  console.log(pad + `asking the person in front (${peopleInFront} people in front of me)`);
  const answer = row(peopleInFront - 1, depth + 1) + 1;
  console.log(pad + `they said ${answer - 1}, so I'm in row ${answer}`);
  return answer;
}
console.log("my row:", row(3));
asking the person in front (3 people in front of me)
  asking the person in front (2 people in front of me)
    asking the person in front (1 people in front of me)
      nobody in front: I'm in row 1
    they said 1, so I'm in row 2
  they said 2, so I'm in row 3
they said 3, so I'm in row 4
my row: 4

The indentation shows how deep the stack is. The lines going in are the calls piling up; the lines coming back out are the unwinding. Every recursion in this episode has the same two parts: a base case, and a step that makes the problem smaller.

Q1: Sum of digits, recursively

Problem. Write sumDigits(n) with recursion. sumDigits(4096) is 4 + 0 + 9 + 6 = 19.

Think out loud. - n % 10 gives the last digit: 4096 % 10 is 6. (% is the remainder after division.) - Math.floor(n / 10) gives the rest: 409. (Math.floor rounds down to a whole number.) - So sumDigits(4096) = 6 + sumDigits(409). Same question, smaller number. - Edge cases: one digit (7), zero (0), and a negative number (-582).

Attempt: the step, but no base case

function sumDigits(n) {
  return (n % 10) + sumDigits(Math.floor(n / 10));
}
console.log(sumDigits(4096));
/home/user/main.js:2
  return (n % 10) + sumDigits(Math.floor(n / 10));
                                   ^

RangeError: Maximum call stack size exceeded

(The first line is the file and line number, then the line itself with ^ under the call.) Why? Follow n: 4096, 409, 40, 4, then 0, and Math.floor(0 / 10) is 0 again, forever. Each call waits on the stack for the next one, and the stack has a limit: about 12,500 frames for a tiny function like this one on this machine (it depends on the machine; see "Going further"). When it's full, JavaScript throws a RangeError (the error type for "a value or size is out of the allowed range"). This is a stack overflow. We forgot the base case.

Fix: a base case first

If n < 10, it's a single digit, so return it. That also covers 0. For a negative number, make it positive first with Math.abs.

function sumDigits(n) {
  if (n < 10) return n;
  return (n % 10) + sumDigits(Math.floor(n / 10));
}
console.log(sumDigits(4096));
console.log(sumDigits(7));
console.log(sumDigits(0));
console.log(sumDigits(Math.abs(-582)));
19
7
0
15

19, 7, 0, 15: all correct. (Without Math.abs, sumDigits(-582) returns -582: a negative number is already < 10.)

Complexity: one call per digit. If d is the number of digits, that's O(d) time and O(d) stack space, because every call waits until the one below returns. (Big-O describes how the work grows as the input grows; O(d) means "in step with d".) A number has at most about 16 digits, so the stack is never a problem here.

Q1b: power(x, n) without **

Problem. Write power(x, n) (x to the power n, for whole numbers n ≥ 0) without the ** operator or Math.pow.

Think out loud. - power(2, 10) = 2 × power(2, 9) = 2 × 2 × power(2, 8) = … = 1024. - Base case: anything to the power 0 is 1. - Real life: compound interest, money that grows by a tiny bit (here 0.01%, a factor of 1.0001) many times: 1.0001 multiplied 100,000 times. - Edge cases: n = 0, n = 1, and a big n.

Attempt: multiply by x, n - 1 each time

We count the calls with a variable outside the function.

let calls = 0;
function power(x, n) {
  calls++;
  if (n === 0) return 1;
  return x * power(x, n - 1);
}
console.log(power(2, 10), "calls:", calls);
calls = 0;
console.log(power(1.0001, 100000), "calls:", calls);
1024 calls: 11
/home/user/main.js:3
  calls++;
  ^

RangeError: Maximum call stack size exceeded

1024 in 11 calls (n = 10, 9, …, 0). Then the same RangeError, and this time there is a base case. Why? n goes down by 1 each time, so power(1.0001, 100000) needs 100,001 calls, all waiting on the stack at once. The stack holds about 12,500. The code is correct, but the recursion is too deep.

Fix: fast power, halve n each time

Real life: counting 1,024 sheets of paper one by one takes 1,024 steps. But fold one sheet in half 10 times and you get 1,024 layers: each fold doubles it. In maths: xⁿ = (x^(n/2))². If n is odd, the halves don't cover it, so multiply by one extra x: 2⁵ = 2² × 2² × 2.

let calls = 0;
function power(x, n) {
  calls++;
  if (n === 0) return 1;
  const half = power(x, Math.floor(n / 2));
  return n % 2 === 0 ? half * half : half * half * x;
}
console.log(power(2, 10), "calls:", calls);
calls = 0;
console.log(power(1.0001, 100000), "calls:", calls);
calls = 0;
console.log(power(5, 0), power(2, 1), "calls:", calls);
1024 calls: 5
22015.45604845634 calls: 18
1 2 calls: 3
  • 1024 in 5 calls instead of 11 (n = 10, 5, 2, 1, 0).
  • The 100,000 case: 22015.45… in only 18 calls, not 100,001.
  • power(5, 0) is 1 and power(2, 1) is 2 (1 + 2 = 3 calls).
  • cond ? a : b (the ternary operator) means "if cond, a, else b".

Complexity: n halves every call, so there are about log₂ n calls (log₂ n = how many times you can halve n before reaching 1; log₂ 100,000 ≈ 17). That's O(log n) time and O(log n) stack. This trick is called fast exponentiation (or exponentiation by squaring).

Trap: calling the half twice. Write power(x, n / 2) * power(x, n / 2) instead of storing half, and every level makes two calls:

let calls = 0;
function power(x, n) {
  calls++;
  if (n === 0) return 1;
  const h = Math.floor(n / 2);
  return n % 2 === 0 ? power(x, h) * power(x, h) : power(x, h) * power(x, h) * x;
}
console.log(power(2, 10), "calls:", calls);
calls = 0;
console.log(power(1.0001, 100000), "calls:", calls);
1024 calls: 31
22015.45604845634 calls: 262143

Still correct, and still only 18 levels deep (so no RangeError), but 262,143 calls instead of 18: back to O(n) work, even worse than n - 1.

Trap: a negative n. Math.floor(-1 / 2) is -1, so n never reaches 0 and fast power overflows too (see the mistakes table). xⁿ for a negative n is 1 / x⁻ⁿ, so handle the sign once: if (n < 0) return 1 / power(x, -n);.

Q2: All permutations of a string

Problem. Return every permutation of a string: every way to arrange all its letters.

Think out loud. - "abc" has six: abc acb bac bca cab cba. - 3 choices for the first place, 2 for the second, 1 for the last: 3 × 2 × 1 = 6. That product is 3 factorial, written 3!. n letters give n! arrangements. - Real life: three friends standing in a row for a photo. - Edge cases: any length; repeated letters ("aab"); the empty string.

Attempt: one loop per place

function permutations(s) {
  const out = [];
  for (const a of s)
    for (const b of s)
      for (const c of s)
        if (a !== b && b !== c && a !== c) out.push(a + b + c);
  return out;
}
console.log(permutations("abc"));
console.log(permutations("abcd").length, permutations("abcd").slice(0, 4));
[ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]
24 [ 'abc', 'abd', 'acb', 'acd' ]

"abc": all six, correct. "abcd": 24, the right count by luck (4 × 3 × 2 three-letter strings also happen to be 24), but look: abc, abd… three letters each. Three loops build three-letter strings; four letters need four loops, five need five. The number of loops depends on the input, and you can't write a variable number of loops by hand. But a function can call itself as many times as it needs.

Fix: pick the first letter, permute the rest

The photo again: 1. Decide who stands first: try a, then b, then c (a loop over each letter). 2. Say a is first. Now arrange b and c: the same question, one person fewer (a recursive call on the rest). 3. One person left: only one way to stand (the base case). 4. Put a in front of every arrangement of the rest: abc, acb. Then b first, then c first.

function permutations(s) {
  if (s.length <= 1) return [s];
  const out = [];
  for (let i = 0; i < s.length; i++) {
    const rest = s.slice(0, i) + s.slice(i + 1);
    for (const p of permutations(rest)) out.push(s[i] + p);
  }
  return out;
}
console.log(permutations("abc"));
console.log(permutations("abcd").length);
console.log(permutations("aab"));
console.log([...new Set(permutations("aab"))]);
console.log(permutations(""));
[ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]
24
[ 'aab', 'aba', 'aab', 'aba', 'baa', 'baa' ]
[ 'aab', 'aba', 'baa' ]
[ '' ]
  • s.slice(0, i) + s.slice(i + 1) is the string without letter i.
  • "abc" gives 6, "abcd" gives 24 four-letter strings.
  • "aab" gives 6, with aab and aba twice each: the two a's look the same, so swapping them gives the same string.
  • A Set is a collection that keeps only unique values. [...new Set(list)] turns the list into a Set (dropping repeats) and back into an array with the spread syntax ... (which spreads the values out one by one): [ 'aab', 'aba', 'baa' ].
  • The empty string has one arrangement: the empty string, [ '' ].

The recursion tree for "abc" (each box is one call; the letter on the arrow is the one put first):

                         permutations("abc")
            a /                   | b                 \ c
   permutations("bc")    permutations("ac")    permutations("ab")
     b /     \ c           a /     \ c           a /     \ b
   ("c")    ("b")        ("c")    ("a")        ("b")    ("a")     <- base case: [s]
     |        |            |        |            |        |
    abc      acb          bac      bca          cab      cba

The tree is only 3 levels deep, so the stack holds at most 3 or 4 frames. What grows is the number of leaves (the results): n!. Factorial is itself a tiny recursion (n! = n × (n - 1)!, base case 1! = 1):

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}
for (const n of [3, 4, 5, 8, 10, 12]) console.log(`${n} letters: ${factorial(n)} permutations`);
3 letters: 6 permutations
4 letters: 24 permutations
5 letters: 120 permutations
8 letters: 40320 permutations
10 letters: 3628800 permutations
12 letters: 479001600 permutations

Complexity: n! results, each n letters long, so O(n · n!) time and space. The stack is only O(n) deep. The output is what's huge: 10 letters already give over 3.6 million strings.

Q3: All subsets

Problem. Return every subset of a list: any selection, from nothing to everything; order doesn't matter ([onion, corn] is the same as [corn, onion]). All the subsets together are called the power set.

Think out loud. - Real life: every pizza you can make from three toppings, onion, paneer and corn, including a plain pizza with none. - Edge cases: the empty list; how many subsets do n items have?

Attempt: loops for singles and pairs

function subsets(items) {
  const out = [[]];
  for (let i = 0; i < items.length; i++) {
    out.push([items[i]]);
    for (let j = i + 1; j < items.length; j++) out.push([items[i], items[j]]);
  }
  return out;
}
const toppings = ["onion", "paneer", "corn"];
console.log(subsets(toppings).length, subsets(toppings));
7 [
  [],
  [ 'onion' ],
  [ 'onion', 'paneer' ],
  [ 'onion', 'corn' ],
  [ 'paneer' ],
  [ 'paneer', 'corn' ],
  [ 'corn' ]
]

Seven pizzas: plain, singles, pairs. But where is [ 'onion', 'paneer', 'corn' ], all three? We wrote loops for sizes 0, 1 and 2. Size 3 needs another loop, and 4 toppings would need yet another. Same problem as permutations: a fixed number of loops for a variable size.

Fix: yes or no for each item (include / exclude)

At the pizza counter, ask one question per topping. Onion: yes or no? Each answer leads to different pizzas, so that's two recursive calls: one that includes the item and one that excludes it. Then paneer, then corn: 2 × 2 × 2 = 8 pizzas. For n items, 2ⁿ subsets. After trying everything with onion, take the onion off again to try the "no" path. Undoing a choice to try another one is called backtracking.

function subsets(items, i = 0, picked = [], out = []) {
  if (i === items.length) {
    out.push([...picked]);
    return out;
  }
  picked.push(items[i]);
  subsets(items, i + 1, picked, out);
  picked.pop();
  subsets(items, i + 1, picked, out);
  return out;
}
const toppings = ["onion", "paneer", "corn"];
console.log(subsets(toppings).length, subsets(toppings));
console.log(subsets([]));
console.log(subsets(["a", "b", "c", "d"]).length);
8 [
  [ 'onion', 'paneer', 'corn' ],
  [ 'onion', 'paneer' ],
  [ 'onion', 'corn' ],
  [ 'onion' ],
  [ 'paneer', 'corn' ],
  [ 'paneer' ],
  [ 'corn' ],
  []
]
[ [] ]
16
  • i is the item we're deciding; picked holds the choices so far; out collects the results. (i = 0 etc. are default parameters: values used when the caller leaves them out.)
  • Base case: i === items.length, every item is decided, so save the pizza.
  • Yes: picked.push(items[i]), recurse. Undo: picked.pop() (remove the last item). No: recurse again.
  • Save a copy: [...picked] makes a new array with the same items. picked keeps changing, so saving picked itself would save the same array 8 times (see "Going further").
  • Results: 8 subsets from all three toppings down to the plain one; the empty list has one subset, the empty one ([ [] ]); 4 items give 16.

The decision tree for 3 items (+ = include, - = exclude; each leaf is one saved subset, in the order they are printed):

                                []
              +onion /                    \ -onion
             [onion]                        []
       +paneer /    \ -paneer       +paneer /    \ -paneer
   [onion,paneer]  [onion]          [paneer]       []
     +c /  \ -c    +c /  \ -c       +c /  \ -c    +c /  \ -c
  [o,p,c] [o,p] [o,c]  [o]       [p,c]   [p]    [c]    []      <- i === 3: save a copy

Complexity: 2ⁿ subsets, each up to n items, so O(n · 2ⁿ) time and space. The stack is only n + 1 deep, one call per decision: O(n).

When the stack runs out

RangeError: Maximum call stack size exceeded has two causes:

  1. No base case, or a step that never reaches it: Math.floor(0 / 10) is 0; Math.floor(-1 / 2) is -1; count(-1) counting down to 0.
  2. Correct but too deep: n - 1 on a big n. Then shrink the problem faster (halve it, like fast power), or write a loop (below).

Depths today: sum of digits O(d), fast power O(log n), permutations and subsets O(n). All small. Check the depth, not just the answer.

Going further

Measure the stack depth limit for real

A counter that goes up on every call, and a catch that catches the RangeError:

let depth = 0;
function dive() {
  depth++;
  dive();
}
try {
  dive();
} catch (err) {
  console.log(err.constructor.name + ":", err.message);
  console.log("tiny function, depth reached:", depth);
}
let depth2 = 0;
function diveBig(a, b, c, d, e) {
  depth2++;
  const x = a + b, y = c + d, z = e * 2;
  diveBig(x, y, z, a, b);
}
try {
  diveBig(1, 2, 3, 4, 5);
} catch (err) {
  console.log("five parameters and three locals, depth reached:", depth2);
}
RangeError: Maximum call stack size exceeded
tiny function, depth reached: 12546
five parameters and three locals, depth reached: 5454

The limit is not a number of calls; it's a size in memory (Node gives the stack about 1 MB by default). Bigger frames (more parameters and local variables) mean fewer calls fit. The exact numbers depend on the machine, the Node version and the function, so never rely on them: on your computer they will likely differ. Note that the RangeError can be caught like any other error, but by then the work is lost.

Turn sumDigits into a loop

Any recursion where the call is the last step can become a loop: the loop variable plays the role of the parameter, and there's no stack to fill.

function sumDigitsLoop(n) {
  n = Math.abs(n);
  let sum = 0;
  while (n >= 10) {
    sum += n % 10;
    n = Math.floor(n / 10);
  }
  return sum + n;
}
console.log(sumDigitsLoop(4096), sumDigitsLoop(7), sumDigitsLoop(0), sumDigitsLoop(-582));

const huge = "9".repeat(100000);
function sumDigitStr(s) {
  if (s.length === 0) return 0;
  return Number(s[s.length - 1]) + sumDigitStr(s.slice(0, -1));
}
try {
  console.log(sumDigitStr(huge));
} catch (err) {
  console.log("recursive:", err.message);
}
let total = 0;
for (const ch of huge) total += Number(ch);
console.log("loop:", total);
19 7 0 15
recursive: Maximum call stack size exceeded
loop: 900000

A real number has at most 16 or so digits, so recursion is fine there. But a string of 100,000 digits needs 100,001 frames: the recursion overflows while the loop happily answers 900000.

Power with BigInt for exact big results

A JavaScript number keeps only about 16 significant digits, so 2 ** 100 is rounded. A BigInt (a whole number of any size, written with an n at the end, like 2n) is exact. Fast power works the same with BigInt: n / 2n already rounds down for BigInts.

console.log(2 ** 100);
console.log(2n ** 100n);
function powerBig(x, n) {
  if (n === 0n) return 1n;
  const half = powerBig(x, n / 2n);
  return n % 2n === 0n ? half * half : half * half * x;
}
console.log(powerBig(2n, 100n));
console.log(powerBig(2n, 100n) === 2n ** 100n);
console.log(2 ** 53 + 1, 2n ** 53n + 1n);
try {
  powerBig(2, 10n);
} catch (err) {
  console.log(err.constructor.name + ":", err.message);
}
1.2676506002282294e+30
1267650600228229401496703205376n
1267650600228229401496703205376n
true
9007199254740992 9007199254740993n
TypeError: Cannot mix BigInt and other types, use explicit conversions
  • 2 ** 53 + 1 prints 9007199254740992: the + 1 is lost. With BigInt it's 9007199254740993.
  • You can't mix a number and a BigInt in one calculation (2 * 1n): JavaScript throws a TypeError (the error for a value of the wrong type). Convert with BigInt(2).
  • For decimals like 1.0001, BigInt doesn't help: it holds whole numbers only.

Permutations without duplicates, without a Set

The Set version still builds all n! strings and throws the repeats away. Better: never build a repeat. Sort the letters so equal letters sit side by side, keep a used array (which letters are already placed), and at each position skip a letter if it equals the previous one and the previous one isn't used (that copy would just repeat the same choice).

function uniquePermutations(s) {
  const letters = [...s].sort();
  const used = new Array(letters.length).fill(false);
  const out = [];
  function build(current) {
    if (current.length === letters.length) {
      out.push(current);
      return;
    }
    for (let i = 0; i < letters.length; i++) {
      if (used[i]) continue;
      if (i > 0 && letters[i] === letters[i - 1] && !used[i - 1]) continue;
      used[i] = true;
      build(current + letters[i]);
      used[i] = false;
    }
  }
  build("");
  return out;
}
console.log(uniquePermutations("aab"));
console.log(uniquePermutations("aabb").length, uniquePermutations("aabb"));
console.log(uniquePermutations("aaaaaaaa"));
[ 'aab', 'aba', 'baa' ]
6 [ 'aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa' ]
[ 'aaaaaaaa' ]

[...s] splits the string into an array of letters; .sort() puts them in order. For "aaaaaaaa" the Set version would build 40,320 identical strings to keep one; this version builds only one. used[i] = false after the call is the backtracking step.

The push(picked) bug, for real

The same subsets code, but saving picked itself instead of a copy:

function subsets(items, i = 0, picked = [], out = []) {
  if (i === items.length) {
    out.push(picked);
    return out;
  }
  picked.push(items[i]);
  subsets(items, i + 1, picked, out);
  picked.pop();
  subsets(items, i + 1, picked, out);
  return out;
}
const result = subsets(["onion", "paneer", "corn"]);
console.log(result.length, result);
console.log(result[0] === result[7]);
8 [
  [], [], [], [],
  [], [], [], []
]
true

Eight empty arrays. An array is stored by reference: out.push(picked) saves a pointer to the same array 8 times, not its contents at that moment. Every push is undone by a pop, so at the end that one array is empty, and all 8 "results" show it. result[0] === result[7] is true: it's literally the same array. Fix: out.push([...picked]).

Complexity summary

Function Time Stack depth Output size
sumDigits(n) O(d), d = number of digits O(d) one number
power(x, n) with n - 1 O(n) O(n): overflows near n ≈ 12,500 here one number
power(x, n) by halving O(log n) O(log n): 18 frames for 100,000 one number
halving, but calling the half twice O(n) O(log n) one number
permutations(s) O(n · n!) O(n) n! strings
subsets(items) O(n · 2ⁿ) O(n): n + 1 frames 2ⁿ arrays
combinations(items, k) (your turn) at most the subsets tree, far less with the early stop O(n) C(n, k) arrays

Common mistakes (and the exact outputs)

Mistake Code What you see Why Fix
No base case return (n % 10) + sumDigits(Math.floor(n / 10)) RangeError: Maximum call stack size exceeded Math.floor(0 / 10) is 0, forever if (n < 10) return n first
Too deep x * power(x, n - 1) with n = 100000 RangeError: Maximum call stack size exceeded 100,001 frames; the stack holds about 12,500 halve n: O(log n) deep
Calling the half twice power(x, h) * power(x, h) 22015.45604845634 calls: 262143 two calls per level const half = power(x, h) once
Negative n in fast power power(2, -2) RangeError: Maximum call stack size exceeded Math.floor(-1 / 2) is -1 if (n < 0) return 1 / power(x, -n)
Negative number in sumDigits sumDigits(-582) -582 it's already < 10 sumDigits(Math.abs(n))
Nested loops for permutations three for loops on "abcd" [ 'abc', 'abd', 'acb', 'acd' ] the loop count is fixed pick first, recurse on the rest
Repeated letters permutations("aab") [ 'aab', 'aba', 'aab', 'aba', 'baa', 'baa' ] equal letters swapped look the same [...new Set(...)], or sort + skip
Loops for subsets one loop per size 7, the full pizza is missing the loop count is fixed include / exclude recursion
Saving without a copy out.push(picked) 8, then eight empty arrays [] the same array, emptied by pop out.push([...picked])
Base case that can be skipped if (n === 0) return [] with count(-1) RangeError: Maximum call stack size exceeded -1, -2, … never equals 0 if (n <= 0) return []

Mini project: every thali under a budget

A canteen sells items one by one. List every thali (any combination of at least one item) that costs at most Rs 100. It's subsets again, with a rule. This time we use the other common way to write subsets: at each call, loop over the items that may come next (from start on), so each call is one saved combination.

The rule lets us prune (cut off a whole branch of the tree without exploring it): sort the items by price; if an item is already too costly for the money left, every later item is too costly as well, so break.

const menu = [
  { name: "paneer", price: 90 },
  { name: "roti", price: 20 },
  { name: "rice", price: 50 },
  { name: "gulab jamun", price: 30 },
  { name: "dal", price: 40 },
];
function thalis(menu, budget, prune = true) {
  const items = [...menu].sort((a, b) => a.price - b.price);
  const out = [];
  let calls = 0;
  function pick(start, picked, left) {
    calls++;
    if (left < 0) return;
    if (picked.length > 0) out.push(`${picked.join(" + ")} = Rs ${budget - left}`);
    for (let i = start; i < items.length; i++) {
      if (prune && items[i].price > left) break;
      picked.push(items[i].name);
      pick(i + 1, picked, left - items[i].price);
      picked.pop();
    }
  }
  pick(0, [], budget);
  return { out, calls };
}
const { out, calls } = thalis(menu, 100);
console.log(out.length, "thalis under Rs 100:");
for (const t of out) console.log("  " + t);
console.log("calls with pruning:", calls);
console.log("calls without pruning:", thalis(menu, 100, false).calls);
13 thalis under Rs 100:
  roti = Rs 20
  roti + gulab jamun = Rs 50
  roti + gulab jamun + dal = Rs 90
  roti + gulab jamun + rice = Rs 100
  roti + dal = Rs 60
  roti + rice = Rs 70
  gulab jamun = Rs 30
  gulab jamun + dal = Rs 70
  gulab jamun + rice = Rs 80
  dal = Rs 40
  dal + rice = Rs 90
  rice = Rs 50
  paneer = Rs 90
calls with pruning: 14
calls without pruning: 29
  • .sort((a, b) => a.price - b.price) sorts from cheapest to costliest (a negative result puts a first).
  • picked.join(" + ") glues the names into one string.
  • Without pruning, the code makes 29 calls: it only notices a thali is too costly after stepping into it (if (left < 0) return). With pruning, 14 calls: it never steps into a costly branch. On a long menu the saving grows fast, because each cut branch would have had its own sub-branches.

Your turn: subsets of size k (solution)

Problem. A pizza deal: choose exactly 2 toppings out of 4. Write combinations(items, k), which returns every subset of size k. A subset of a fixed size is called a combination; order doesn't matter. 4 toppings, choose 2, gives 6 pizzas. The count is written C(n, k) ("n choose k").

Hint from the video: the base case is picked.length === k; stop early if there aren't enough items left to reach k.

let calls = 0;
function combinations(items, k, i = 0, picked = [], out = []) {
  calls++;
  if (picked.length === k) {
    out.push([...picked]);
    return out;
  }
  if (picked.length + (items.length - i) < k) return out;
  picked.push(items[i]);
  combinations(items, k, i + 1, picked, out);
  picked.pop();
  combinations(items, k, i + 1, picked, out);
  return out;
}
const toppings = ["onion", "paneer", "corn", "olive"];
console.log(combinations(toppings, 2).length, combinations(toppings, 2));
console.log(combinations(toppings, 0));
console.log(combinations(toppings, 5));
const twenty = Array.from({ length: 20 }, (_, i) => i + 1);
calls = 0;
console.log("20 choose 2:", combinations(twenty, 2).length, "in", calls, "calls");
6 [
  [ 'onion', 'paneer' ],
  [ 'onion', 'corn' ],
  [ 'onion', 'olive' ],
  [ 'paneer', 'corn' ],
  [ 'paneer', 'olive' ],
  [ 'corn', 'olive' ]
]
[ [] ]
[]
20 choose 2: 190 in 419 calls
  • Base case: picked has k items, so save a copy and stop: there's no need to decide the remaining items (they are all "no").
  • Early stop: picked.length + (items.length - i) is the most items we could still end up with. If that's less than k, this branch can never succeed, so return. This also covers i === items.length.
  • Edge cases: k = 0 gives one empty combination [ [] ]; k = 5 is impossible, [].
  • Array.from({ length: 20 }, (_, i) => i + 1) makes [1, 2, …, 20]. 20 choose 2 is 190; the full include/exclude tree would have about 2 million calls (2²¹ - 1), but the base case and the early stop cut it to a few hundred.

Practice questions (with solutions)

1. Reverse a string recursively. reverse("chai") is "iahc".

Solution
function reverse(s) {
  if (s.length <= 1) return s;
  return reverse(s.slice(1)) + s[0];
}
console.log(reverse("chai"));
console.log(reverse("a"), JSON.stringify(reverse("")));
console.log(reverse("racecar"));
iahc
a ""
racecar

The reverse of a string is the reverse of everything after the first letter, followed by the first letter. Base case: 0 or 1 letters. O(n) deep, and O(n²) time, because each slice copies the string.

2. Flatten a nested array. [1, [2, [3, [4]], 5]] → [1, 2, 3, 4, 5], without .flat().

Solution
function flatten(arr) {
  const out = [];
  for (const item of arr) {
    if (Array.isArray(item)) out.push(...flatten(item));
    else out.push(item);
  }
  return out;
}
const nested = [1, [2, [3, [4]], 5], [], [[6]]];
console.log(flatten(nested));
console.log(nested.flat(Infinity));
console.log(flatten([]));
[ 1, 2, 3, 4, 5, 6 ]
[ 1, 2, 3, 4, 5, 6 ]
[]

Array.isArray(x) is true only for arrays. Each nested array is the same question, smaller. The base case is hidden: a plain value is pushed without recursing. Depth = how deeply the arrays are nested. .flat(Infinity) is the built-in way.

Quick quiz

function count(n) {
  if (n === 0) return [];
  return [...count(n - 1), n];
}
console.log(count(3));
try {
  console.log(count(-1));
} catch (err) {
  console.log(err.constructor.name + ":", err.message);
}

(In the video the second line had no try/catch; we add one here so the program prints the error neatly instead of crashing.)

A) [ 3, 2, 1 ], then [] B) [ 1, 2, 3 ], then [] C) [ 1, 2, 3 ], then a RangeError D) [ 3, 2, 1 ], then a RangeError

Answer
[ 1, 2, 3 ]
RangeError: Maximum call stack size exceeded

C. count(3) builds count(2) first, then adds 3 at the end: [ 1, 2, 3 ]. count(-1) goes -2, -3, … and never reaches 0: RangeError: Maximum call stack size exceeded. The base case should be n <= 0.

Interview questions

  1. What is recursion? A function that solves a problem by calling itself on a smaller version of it, until a base case it can answer directly.
  2. What happens without a base case? The calls never stop, the call stack fills up, and JavaScript throws RangeError: Maximum call stack size exceeded.
  3. Can a correct recursion still overflow? Yes, if it's too deep (n - 1 with n = 100,000). Make it shallower (halving) or use a loop.
  4. How does fast power work? xⁿ = (x^(n/2))², times x if n is odd. Compute the half once: O(log n).
  5. How many permutations does a string of n distinct letters have? n!. Generating them is O(n · n!).
  6. How do you handle repeated letters? Wrap the result in a Set, or sort the letters and skip a letter equal to the previous unused one (so repeats are never built).
  7. How many subsets do n items have, and how do you list them? 2ⁿ; include / exclude recursion, or loop over the next items from a start index.
  8. What is backtracking? Making a choice, exploring everything that follows, then undoing it (pop) to try the next choice. Pruning cuts branches that can't succeed.
  9. Why [...picked] and not picked? Arrays are stored by reference; without a copy, every saved result is the same array, empty at the end.
  10. Recursion or loop? Recursion is clearer for trees and choices (permutations, subsets, nested data). For a simple chain like a countdown or sum of digits, a loop uses no stack and can't overflow.

Glossary

Term Meaning
Recursion A function that calls itself on a smaller version of the problem
Recursive function A function that uses recursion
Base case The input small enough to answer without calling again
Recursive case The step that calls the function again on a smaller input
Call stack The list of calls that have started but not finished; the newest is on top
Stack frame One call's entry on the stack: its parameters and local variables
Stack overflow The call stack is full because the recursion is endless or too deep
RangeError JavaScript's error for a value or size outside the allowed range, including "Maximum call stack size exceeded"
TypeError JavaScript's error for a value of the wrong type (for example mixing a number and a BigInt)
Unwinding The waiting calls finishing one by one after the base case returns
Recursion tree A drawing of every call: each call's children are the calls it makes
Leaf A call at the bottom of the tree that makes no more calls (one result)
Depth How many frames are on the stack at the deepest point
% (remainder) What is left after division: 4096 % 10 is 6
Math.floor / Math.abs Round down to a whole number / drop the minus sign
Ternary operator cond ? a : b: a if cond is true, else b
Fast exponentiation Computing xⁿ from x^(n/2), squared: O(log n) multiplications
O(log n) Work that grows like the number of times you can halve n (17 for 100,000)
O(n), O(n · n!), O(n · 2ⁿ) Work that grows in step with n / with n times n factorial / with n times 2 to the n
Big-O How the work grows as the input grows
Permutation One way to arrange all the items in order
Factorial (n!) n × (n - 1) × … × 1: the number of permutations of n distinct items
Subset Any selection of items, from none to all; order doesn't matter
Power set The set of all subsets of a list: 2ⁿ of them
Combination A subset of a fixed size k; C(n, k) of them
Include / exclude For each item, one call that takes it and one that doesn't
Backtracking Make a choice, explore, then undo it to try the next choice
Pruning Skipping a whole branch that can't lead to a valid answer
Set A collection that keeps only unique values
Spread (...) Spreads out the values of an array, string or Set: [...picked] copies an array
Reference How arrays and objects are stored: two variables can point to the same array
Default parameter A value a parameter gets when the caller leaves it out: i = 0
push / pop Add an item to / remove the last item from the end of an array
slice Copy part of a string or array: s.slice(0, i)
BigInt A whole number of any size, written with n: 2n ** 100n
JSON.stringify Turns a value into text, so "" (an empty string) is visible when printed
try / catch Run code and handle an error it throws instead of crashing

Summary

  • Recursion = a base case + a step that makes the problem smaller. Calls wait on the call stack and unwind when the base case returns.
  • RangeError: Maximum call stack size exceeded means no base case (or one you never reach), or a correct recursion that's too deep. The limit is about 12,500 small frames here, and it depends on the machine.
  • sumDigits = n % 10 + sumDigits(Math.floor(n / 10)), base case n < 10; use Math.abs for negatives. Fast power halves n and stores half once: O(log n).
  • Permutations: pick each letter first, recurse on the rest; Set (or sort + skip) for repeats. O(n · n!).
  • Subsets: include / exclude with push, recurse, pop, recurse; save a copy [...picked]. O(n · 2ⁿ). Add a size limit and an early stop for combinations, and prune with a budget.
  • Next episode: searching and sorting questions: binary search for the first and last position, merge sort (recursion again), and sorting objects by two keys.