// ─────────────────────────────────────────────────────────────────────────────
// RECURSION
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : a function defined in terms of smaller instances of itself; base case stops it.
// TELL   : "nested", "tree / list shaped", "defined in terms of itself", "divide and conquer",
//          "all combinations", "flatten", "deep".
// SAY    : base case, recursive case, call stack / stack frame, recursion depth, memoization,
//          tail call, divide and conquer, "trust the recursion" (assume the sub-call is correct),
//          mutual recursion, explicit stack (iterative conversion).
// BIG-O  : time = number of calls x work per call; space = max depth of the call stack.
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── 1. Anatomy  —  (a) base case returns directly; (b) recursive case makes the input smaller and TRUSTS the sub-result
function factorial(n) {
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive case: assume factorial(n-1) is right
}
assert.equal(factorial(5), 120);
assert.equal(factorial(0), 1);

// ── 2. Fast exponentiation (exponentiation by squaring)  —  x^n = (x^(n/2))^2 * (x if n odd)  —  O(log n) / O(log n) stack
function power(x, n) {
  if (n === 0) return 1;
  if (n < 0) return 1 / power(x, -n);
  const half = power(x, Math.floor(n / 2));
  return n % 2 === 0 ? half * half : half * half * x;
}
assert.equal(power(2, 10), 1024);
assert.equal(power(2, -2), 0.25);
assert.equal(power(7, 0), 1);

// ── 3. Sum of digits  —  last digit + sum of the rest  —  O(digits)
const sumDigits = (n) => (n < 10 ? n : (n % 10) + sumDigits(Math.floor(n / 10)));
assert.equal(sumDigits(1234), 10);
assert.equal(sumDigits(0), 0);
assert.equal(sumDigits(9), 9);

// ── 4. Reverse string recursively  —  reverse(rest) + first  —  O(n) / O(n) stack (O(n^2) with string concat; fine as a demo)
const reverseStr = (s) => (s.length <= 1 ? s : reverseStr(s.slice(1)) + s[0]);
assert.equal(reverseStr('hello'), 'olleh');
assert.equal(reverseStr(''), '');
assert.equal(reverseStr('a'), 'a');

// ── 5. Flatten nested arrays  —  for each item: array ? recurse : push  —  O(total items) / O(depth)
function flatten(arr, out = []) {
  for (const x of arr) Array.isArray(x) ? flatten(x, out) : out.push(x);
  return out;
}
assert.deepEqual(flatten([1, [2, [3, [4]], 5]]), [1, 2, 3, 4, 5]);
assert.deepEqual(flatten([]), []);
assert.deepEqual(flatten([[[]]]), []);
assert.deepEqual([1, [2, [3]]].flat(Infinity), [1, 2, 3]); // built-in equivalent

// ── 6. Deep clone (plain data)  —  arrays map recursively; objects rebuild from entries; primitives returned as is  —  O(n)
function deepClone(v) {
  if (Array.isArray(v)) return v.map(deepClone);
  if (v !== null && typeof v === 'object') return Object.fromEntries(Object.entries(v).map(([k, x]) => [k, deepClone(x)]));
  return v;
}
const orig = { a: [1, { b: 2 }], c: null };
const copy = deepClone(orig);
assert.deepEqual(copy, orig);
assert.notEqual(copy.a, orig.a);
assert.notEqual(copy.a[1], orig.a[1]);
assert.equal(deepClone(5), 5);
// NOTE: structuredClone(v) exists in Node 17+; handles Map/Set/Date/cycles but not functions.

// ── 7. Tower of Hanoi  —  move n-1 to aux, move 1 to target, move n-1 from aux to target  —  O(2^n) moves
function hanoi(n, from = 'A', to = 'C', via = 'B', moves = []) {
  if (n === 0) return moves;
  hanoi(n - 1, from, via, to, moves);
  moves.push([from, to]);
  hanoi(n - 1, via, to, from, moves);
  return moves;
}
assert.equal(hanoi(3).length, 7); // 2^n - 1
assert.deepEqual(hanoi(1), [['A', 'C']]);
assert.deepEqual(hanoi(0), []);

// ── 8. Fibonacci: naive vs memoized  —  naive O(phi^n) recomputes; memo Map makes each n computed once  —  O(n) / O(n)
function fibNaive(n) { return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2); }
function fibMemo(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);
  const v = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, v);
  return v;
}
assert.equal(fibNaive(10), 55);
assert.equal(fibMemo(10), 55);
assert.equal(fibMemo(90), 2880067194370816000); // naive would take forever; exact up to fib(78) in doubles, close enough here
assert.equal(fibMemo(0), 0);

// ── 9. Recursion -> iteration with an explicit stack  —  push the initial frame; loop: pop, do work, push sub-frames  —  same O()
//        Worked example: sum of a nested array. Recursive version first, then the stack version.
const sumNestedRec = (arr) => arr.reduce((s, x) => s + (Array.isArray(x) ? sumNestedRec(x) : x), 0);
function sumNestedIter(arr) {
  const stack = [arr]; // frames = things still to process
  let sum = 0;
  while (stack.length) {
    const cur = stack.pop();
    if (Array.isArray(cur)) stack.push(...cur); // "recurse" = push children
    else sum += cur;
  }
  return sum;
}
const nested = [1, [2, [3, [4, [5]]]], 6];
assert.equal(sumNestedRec(nested), 21);
assert.equal(sumNestedIter(nested), 21);
assert.equal(sumNestedIter([]), 0);
// For in-order tree traversal the iterative form needs a "visited" marker or the classic
// `while (cur || stack.length) { while (cur) { stack.push(cur); cur = cur.left; } cur = stack.pop(); visit; cur = cur.right; }`.

// ── 10. Tail-call note  —  JS spec (ES2015) has proper tail calls but V8/Node do NOT implement TCO. A tail-recursive loop still
//        grows the stack. If depth may exceed ~10^4, convert to a loop or explicit stack.
function sumToTail(n, acc = 0) { return n === 0 ? acc : sumToTail(n - 1, acc + n); } // tail position, still O(n) stack in V8
assert.equal(sumToTail(1000), 500500);

// ── 11. Max recursion depth in Node  —  roughly 10k-12k frames by default (depends on frame size). Deeper => RangeError.
//        Avoid: iterate, use an explicit stack, memoize bottom-up (DP tabulation), or increase --stack-size (not available in assessments).
function depthProbe(n) { try { return depthProbe(n + 1); } catch { return n; } }
const maxDepth = depthProbe(0);
assert.ok(maxDepth > 5000 && maxDepth < 100000, `observed depth ${maxDepth}`);
assert.throws(() => { const f = (n) => f(n + 1) + 1; f(0); }, RangeError); // "Maximum call stack size exceeded"
// A linked-list of 10^5 nodes reversed recursively WILL blow the stack; iterate instead.

// ── 12. Mutual recursion  —  two functions call each other; base case in each  —  O(n)
const isEven = (n) => (n === 0 ? true : isOdd(n - 1));
const isOdd = (n) => (n === 0 ? false : isEven(n - 1));
assert.equal(isEven(10), true);
assert.equal(isOdd(7), true);
assert.equal(isEven(1), false);

console.log('ok: algorithms/recursion.js');