递归算法模式：互递归、记忆化、分治与回溯

function isEven(n) {
  if (n === 0) return true;
  return isOdd(n - 1);
}

function isOdd(n) {
  if (n === 0) return false;
  return isEven(n - 1);
}

console.log(isEven(10));   // true
console.log(isOdd(7));     // true

// 极简求值器：支持数字、加号与括号，如 '2+(3+(4))'
function evalExpr(tokens) {
  let value = evalItem(tokens);          // 第一项：数字或括号组
  while (tokens[0] === '+') {
    tokens.shift();                      // 吃掉 '+'
    value += evalItem(tokens);           // 加号后面又是一项
  }
  return value;
}

function evalItem(tokens) {
  const first = tokens.shift();
  if (first === '(') {
    const inner = evalExpr(tokens);      // 括号里是完整表达式：互递归点
    tokens.shift();                      // 吃掉 ')'
    return inner;
  }
  return Number(first);
}

console.log(evalExpr(['2', '+', '(', '3', '+', '(', '4', ')', ')']));
// 9

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

console.time('朴素版');
console.log(fib(35));          // 9227465
console.timeEnd('朴素版');     // 量级：数十到上百毫秒，且随 n 指数增长

function fibMemo(n, cache = new Map()) {
  if (n <= 1) return n;
  if (cache.has(n)) return cache.get(n);

  const result = fibMemo(n - 1, cache) + fibMemo(n - 2, cache);
  cache.set(n, result);
  return result;
}

console.time('记忆化');
console.log(fibMemo(35));      // 9227465
console.timeEnd('记忆化');     // 量级：零点几毫秒，快三个数量级

function binarySearch(sorted, target) {
  let lo = 0;
  let hi = sorted.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;        // 取中点，位运算等价于 Math.floor((lo+hi)/2)
    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 7));   // 3

function quickSort(arr) {
  if (arr.length <= 1) return arr;                       // 基线
  const [pivot, ...rest] = arr;                          // 拆
  const left = rest.filter((x) => x < pivot);            // 小的一半
  const right = rest.filter((x) => x >= pivot);          // 大的一半
  return [...quickSort(left), pivot, ...quickSort(right)];  // 递归 + 合
}

console.log(quickSort([5, 2, 9, 1, 7]));   // [1, 2, 5, 7, 9]

function permute(items) {
  const result = [];

  function backtrack(path, remaining) {
    if (remaining.length === 0) {
      result.push([...path]);            // 收集一份完整排列的副本
      return;
    }
    for (let i = 0; i < remaining.length; i += 1) {
      path.push(remaining[i]);                        // 1. 选择
      backtrack(path, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);  // 2. 递归
      path.pop();                                     // 3. 撤销
    }
  }

  backtrack([], items);
  return result;
}

console.log(permute(['a', 'b', 'c']));
// [['a','b','c'], ['a','c','b'], ['b','a','c'], ['b','c','a'], ['c','a','b'], ['c','b','a']]

// 深度优先（DFS）：用栈，后进先出
function walkDepth(root, visit) {
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    visit(node);
    for (let i = node.children.length - 1; i >= 0; i -= 1) {
      stack.push(node.children[i]);    // 逆序压入，保证左孩子先处理
    }
  }
}

// 广度优先（BFS）：用队列，先进先出——"一层一层扫"
function walkBreadth(root, visit) {
  const queue = [root];
  while (queue.length > 0) {
    const node = queue.shift();
    visit(node);
    for (const child of node.children) {
      queue.push(child);
    }
  }
}

// 直接风格：结果用 return 给
function add(a, b) { return a + b; }

// CPS：结果通过回调交出去
function addCps(a, b, k) { k(a + b); }

addCps(1, 2, (sum) => console.log(sum));   // 3

function subsets(items) {
  const result = [];
  function backtrack(path, start) {
    result.push(path);
    for (let i = start; i < items.length; i += 1) {
      path.push(items[i]);
      backtrack(path, i + 1);
    }
  }
  backtrack([], 0);
  return result;
}

console.log(subsets([1, 2, 3]));
// 期望 8 个子集，实际是 8 个指向同一个数组的引用，内容全部一样