JavaScript: Recursion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27function factorial(n) {
  if (!Number.isInteger(n) || n < 0) throw new RangeError('factorial needs a whole number 0 or above');
  if (n <= 1) return 1;               // covers 0! and 1!, both of which are 1
  return n * factorial(n - 1);
}

// The loop version. Same answers, no stack frames.
function factorialLoop(n) {
  let total = 1;
  for (let i = 2; i <= n; i++) total *= i;
  return total;
}

// Exact for any size, because BigInt does not round.
function factorialBig(n) {
  return n <= 1n ? 1n : n * factorialBig(n - 1n);
}

const refused = (() => { try { factorial(-1); return 'no error'; } catch (e) { return e.constructor.name; } })();

console.log('0! =', factorial(0), ' 5! =', factorial(5), ' 10! =', factorial(10));
console.log('18! =', factorial(18), '<- still a safe integer');
console.log('19! =', factorial(19), '<- past 2^53, so ±1 stops meaning anything');
console.log('20! + 1 === 20! ?', factorial(20) + 1 === factorial(20));
console.log('23! as a Number:', factorial(23));
console.log('23! as a BigInt:', factorialBig(23n).toString(), '<- the true answer');
console.log('negative input  :', refused);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function gcd(a, b) {
  return b === 0 ? Math.abs(a) : gcd(b, a % b);
}

// The same steps as a loop. Nothing is lost, because the recursive call is the
// last thing that happens (tail recursion).
function gcdLoop(a, b) {
  while (b !== 0) [a, b] = [b, a % b];
  return Math.abs(a);
}

// GCD gives you LCM for free. Divide first, so the product cannot overflow.
const lcm = (a, b) => Math.abs(a / gcd(a, b) * b);

// Extends to a whole list by folding.
const gcdAll = (nums) => nums.reduce(gcd);

for (const [a, b] of [[48, 18], [17, 5], [270, 192], [0, 5]]) {
  console.log(`gcd(${a}, ${b}) =`, gcd(a, b), ' lcm =', lcm(a, b));
}
console.log('gcd of the whole list:', gcdAll([24, 36, 60]));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16// Both ends excluded: range(2, 9) is [3..8], matching the source's example.
function range(x, y) {
  if (x + 1 >= y) return [];               // nothing in between
  return [x + 1, ...range(x + 1, y)];
}

// The inclusive version most other languages mean by "range".
const rangeInclusive = (x, y) => (x > y ? [] : [x, ...rangeInclusive(x + 1, y)]);

// No recursion at all, for comparison.
const rangeBuiltIn = (x, y) => Array.from({ length: Math.max(0, y - x - 1) }, (_, i) => x + 1 + i);

console.log('range(2, 9)          =', range(2, 9));
console.log('rangeInclusive(2, 9) =', rangeInclusive(2, 9));
console.log('range(2, 3)          =', range(2, 3), '<- adjacent, so nothing between');
console.log('range(9, 2)          =', range(9, 2), '<- backwards, so nothing at all');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30// The version everyone writes first. Readable, and quietly O(n^2) on memory:
// each call allocates a fresh `rest` array.
function sumCopying(values) {
  if (values.length === 0) return 0;          // empty is the real base case
  const [first, ...rest] = values;
  return first + sumCopying(rest);
}

// Same recursion, no copying: walk an index instead of shrinking the array.
function sumIndexed(values, i = 0) {
  if (i >= values.length) return 0;
  return values[i] + sumIndexed(values, i + 1);
}

// Count the arrays each version allocates, to make the difference visible.
let copies = 0;
function sumCounted(values) {
  if (values.length === 0) return 0;
  const [first, ...rest] = values;
  copies++;
  return first + sumCounted(rest);
}
sumCounted([1, 2, 3, 4, 5, 6]);

const nums = [1, 2, 3, 4, 5, 6];

console.log('sumCopying :', sumCopying(nums));
console.log('sumIndexed :', sumIndexed(nums));
console.log('reduce     :', nums.reduce((a, b) => a + b, 0));
console.log('arrays allocated for 6 items:', copies);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32// Straightforward: n multiplications, so n stack frames.
function power(base, exp) {
  if (exp === 0) return 1;
  if (exp < 0) return 1 / power(base, -exp);
  return base * power(base, exp - 1);
}

// Exponentiation by squaring: about log2(n) steps instead of n.
function powerFast(base, exp) {
  if (exp === 0) return 1;
  if (exp < 0) return 1 / powerFast(base, -exp);
  const half = powerFast(base, Math.floor(exp / 2));
  return exp % 2 === 0 ? half * half : half * half * base;
}

// Count the calls so the difference is not just a claim.
let slow = 0;
let fast = 0;
const countSlow = (b, e) => { slow++; return e === 0 ? 1 : b * countSlow(b, e - 1); };
const countFast = (b, e) => {
  fast++;
  if (e === 0) return 1;
  const h = countFast(b, Math.floor(e / 2));
  return e % 2 === 0 ? h * h : h * h * b;
};
countSlow(2, 1024);
countFast(2, 1024);

console.log("8^2 =", power(8, 2), "  (the source's example)");
console.log('2^10 =', power(2, 10));
console.log('2^-2 =', power(2, -2));
console.log('calls for 2^1024 — plain:', slow, ' by squaring:', fast);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36// The textbook definition. Also the textbook example of accidental waste:
// fib(n - 1) and fib(n - 2) recompute overlapping work.
function fib(n) {
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
}

// Remember what you already worked out.
function fibMemo(n, seen = new Map()) {
  if (n < 2) return n;
  if (seen.has(n)) return seen.get(n);
  const value = fibMemo(n - 1, seen) + fibMemo(n - 2, seen);
  seen.set(n, value);
  return value;
}

const firstN = (n) => Array.from({ length: n }, (_, i) => fibMemo(i));

// Count the calls each way.
let plain = 0;
let memo = 0;
const countPlain = (n) => { plain++; return n < 2 ? n : countPlain(n - 1) + countPlain(n - 2); };
const countMemo = (n, seen = new Map()) => {
  memo++;
  if (n < 2) return n;
  if (seen.has(n)) return seen.get(n);
  const v = countMemo(n - 1, seen) + countMemo(n - 2, seen);
  seen.set(n, v);
  return v;
};
countPlain(25);
countMemo(25);

console.log('first 10   :', firstN(10));
console.log('fib(25)    :', fib(25));
console.log('calls for fib(25) — plain:', plain, ' memoised:', memo);
console.log('fib(90)    :', fibMemo(90), '<- already past safe integers');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23// Mutual recursion: each function's base case is the other's exit.
function isEven(n) {
  n = Math.abs(n);
  return n === 0 ? true : isOdd(n - 1);
}
function isOdd(n) {
  n = Math.abs(n);
  return n === 0 ? false : isEven(n - 1);
}

// What you would actually write. Constant time, no stack, no limit.
const isEvenFast = (n) => n % 2 === 0;

// Prove the limit rather than assert it in a comment.
const overflowed = (() => {
  try { isEven(1e6); return 'no error'; } catch (e) { return e.constructor.name; }
})();

console.log('isEven(10) :', isEven(10));
console.log('isOdd(7)   :', isOdd(7));
console.log('isEven(0)  :', isEven(0));
console.log('isEven(1e6):', overflowed, '<- one stack frame per step down');
console.log('isEvenFast(1e6):', isEvenFast(1e6), '<- no recursion, no limit');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35// Recursion by slicing. Simple to read, and it copies at every level.
function search(sorted, target) {
  if (sorted.length === 0) return null;

  const mid = Math.floor(sorted.length / 2);
  if (sorted[mid] === target) return sorted[mid];

  return sorted[mid] < target
    ? search(sorted.slice(mid + 1), target)   // right half
    : search(sorted.slice(0, mid), target);   // left half
}

// Count the arrays allocated, since that is the cost being hidden.
let slices = 0;
function searchCounted(sorted, target) {
  if (sorted.length === 0) return null;
  const mid = Math.floor(sorted.length / 2);
  if (sorted[mid] === target) return sorted[mid];
  slices++;
  return sorted[mid] < target
    ? searchCounted(sorted.slice(mid + 1), target)
    : searchCounted(sorted.slice(0, mid), target);
}

const sample = [0, 1, 2, 3, 4, 5, 6];
searchCounted(sample, 6);

// Why the source's sample is ambiguous: here value and index are the same number.
const shifted = [10, 20, 30, 40, 50, 60, 70];

console.log("search(sample, 5) =", search(sample, 5), "<- the source's expected '5'");
console.log('but in this array value and index differ:');
console.log('search(shifted, 50) =', search(shifted, 50), '(index would be 4)');
console.log('missing target      :', search(sample, 99));
console.log('arrays copied looking for 6:', slices);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39function mergeSort(values, compare = (a, b) => a - b) {
  if (values.length <= 1) return values.slice();     // copy, so the input is safe

  const mid = Math.floor(values.length / 2);
  const left = mergeSort(values.slice(0, mid), compare);
  const right = mergeSort(values.slice(mid), compare);
  return merge(left, right, compare);
}

function merge(left, right, compare) {
  const out = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    // <= , not < : ties take from the LEFT, which is what makes it stable.
    out.push(compare(left[i], right[j]) <= 0 ? left[i++] : right[j++]);
  }
  // One side is empty now; whatever is left is already in order.
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

const sample = [34, 7, 23, 32, 5, 62];

// Stability: equal keys must keep their original order.
const bookings = [
  { name: 'Ada', seats: 2 },
  { name: 'Bode', seats: 1 },
  { name: 'Chidi', seats: 2 },
  { name: 'Dele', seats: 1 },
];
const bySeats = mergeSort(bookings, (a, b) => a.seats - b.seats);

console.log("the source's sample:", mergeSort(sample));
console.log('input afterwards  :', sample, '<- unchanged');
console.log('stable by seats   :', bySeats.map((b) => b.name));
console.log("sort() on numbers :", [10, 9, 100].slice().sort(), '<- compares as TEXT');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18function isPalindrome(text) {
  if (text.length <= 1) return true;                       // '' and 'a'
  if (text[0] !== text[text.length - 1]) return false;
  return isPalindrome(text.slice(1, -1));                  // drop both ends
}

// The version that copes with a real sentence: normalise, then check.
const clean = (text) => text.toLowerCase().replace(/[^a-z0-9]/g, '');
const isPalindromeSentence = (text) => isPalindrome(clean(text));

// A completely different method, as a cross-check.
const byReversal = (text) => text === [...text].reverse().join('');

for (const w of ['madam', 'abdb', 'ab', 'a', '']) {
  console.log(JSON.stringify(w).padEnd(8), '->', isPalindrome(w));
}
console.log('A man, a plan, a canal - Panama ->', isPalindromeSentence('A man, a plan, a canal - Panama'));
console.log('cleaned:', clean('A man, a plan, a canal - Panama'));

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26function binaryToDecimal(bits) {
  if (!/^[01]+$/.test(bits)) throw new SyntaxError('binary digits only');
  return convert(bits);
}

// From the right: last digit is the 1s place, the rest is worth double.
function convert(bits) {
  if (bits.length === 0) return 0;
  const last = Number(bits[bits.length - 1]);
  return last + 2 * convert(bits.slice(0, -1));
}

// From the left, which needs no slicing arithmetic at the end.
const fromLeft = (bits, acc = 0) =>
  bits.length === 0 ? acc : fromLeft(bits.slice(1), acc * 2 + Number(bits[0]));

const rejected = (() => {
  try { binaryToDecimal('1102'); return 'no error'; } catch (e) { return e.constructor.name; }
})();

console.log("'1101'   ->", binaryToDecimal('1101'));
console.log("'11111111' ->", binaryToDecimal('11111111'));
console.log('--- what the built-ins do with the invalid "1102" ---');
console.log("parseInt('1102', 2) =", parseInt('1102', 2), '<- silently stops at the 2 and returns 6');
console.log("Number('0b1102')    =", Number('0b1102'), '<- NaN, which at least tells you');
console.log('ours                =', rejected, '<- refuses outright');

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30function binarySearch(sorted, target, low = 0, high = sorted.length - 1) {
  if (low > high) return -1;                 // the range is empty: not here

  const mid = low + Math.floor((high - low) / 2);
  if (sorted[mid] === target) return mid;

  return sorted[mid] < target
    ? binarySearch(sorted, target, mid + 1, high)
    : binarySearch(sorted, target, low, mid - 1);
}

// Count the calls, to show it is log2(n) and not n.
let calls = 0;
function counted(sorted, target, low = 0, high = sorted.length - 1) {
  calls++;
  if (low > high) return -1;
  const mid = low + Math.floor((high - low) / 2);
  if (sorted[mid] === target) return mid;
  return sorted[mid] < target
    ? counted(sorted, target, mid + 1, high)
    : counted(sorted, target, low, mid - 1);
}

const data = [1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 17, 19, 20, 22, 23];
counted(data, 23);

console.log("looking for 6  ->", binarySearch(data, 6), "(the source expects 4)");
console.log('looking for 16 ->', binarySearch(data, 16), '(the source expects -1)');
console.log('15 items, calls to find the last one:', calls);
console.log('a linear scan would need:', data.length);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32// The mapping is derived from the source's own expected output, which does NOT
// match a phone keypad. "12" -> "ad".. means 1 is 'abc' and 2 is 'def', and
// "9" -> ["y","z"] means 9 is 'yz'. That is the alphabet cut into threes:
// 1 abc, 2 def, 3 ghi, 4 jkl, 5 mno, 6 pqr, 7 stu, 8 vwx, 9 yz.
const ALPHABET = 'abcdefghijklmnopqrstuvwxyz';
const lettersFor = (digit) => ALPHABET.slice((Number(digit) - 1) * 3, Number(digit) * 3);

function combinations(digits) {
  if (digits === '') return [];                 // no digits, no combinations

  const heads = lettersFor(digits[0]).split('');
  const tails = combinations(digits.slice(1));

  // Last digit: the letters themselves are the answers.
  if (tails.length === 0) return heads;
  return heads.flatMap((h) => tails.map((t) => h + t));
}

// The real phone keypad, for contrast, since the prompt's wording implies it.
const KEYPAD = { 2: 'abc', 3: 'def', 4: 'ghi', 5: 'jkl', 6: 'mno', 7: 'pqrs', 8: 'tuv', 9: 'wxyz' };
const keypadCombos = (digits) => {
  if (digits === '') return [];
  const heads = KEYPAD[digits[0]].split('');
  const tails = keypadCombos(digits.slice(1));
  return tails.length === 0 ? heads : heads.flatMap((h) => tails.map((t) => h + t));
};

console.log("mapping: 1 ->", lettersFor('1'), ' 2 ->', lettersFor('2'), ' 9 ->', lettersFor('9'));
console.log('combinations("12") =', combinations('12'));
console.log('combinations("9")  =', combinations('9'));
console.log('how many for "123":', combinations('123').length, '= 3 x 3 x 3');
console.log('on a real keypad, "23" would be:', keypadCombos('23'));