递归与尾调用优化

1. 递归基础

1.1 递归定义

递归（Recursion）是函数直接或间接调用自身的编程技术。每个递归必须包含：

• 基线条件（Base Case）：停止递归的条件
• 递归条件（Recursive Case）：将问题分解为更小的子问题

function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);
}

console.log(factorial(5)); // 120

1.2 递归调用栈

factorial(4) 的调用栈：
factorial(4) = 4 * factorial(3)
             = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1 = 24

2. 常见递归模式

// 数组求和
function sum(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sum(arr.slice(1));
}

// 反转字符串
function reverse(str) {
  if (str.length <= 1) return str;
  return reverse(str.slice(1)) + str[0];
}

// 二分查找
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] > target) return binarySearch(arr, target, left, mid - 1);
  return binarySearch(arr, target, mid + 1, right);
}

// 快速排序
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = arr.slice(1).filter((x) => x <= pivot);
  const right = arr.slice(1).filter((x) => x > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

3. 尾调用优化（TCO）

3.1 尾调用定义

尾调用（Tail Call）是指函数的最后一步是调用另一个函数：

// 尾调用
function tailCall(x) {
  return anotherFunction(x);
}

// 非尾调用
function notTailCall(x) {
  return anotherFunction(x) + 1;
}

3.2 尾递归改写

// 普通递归 → 尾递归
function factorial(n, acc = 1) {
  if (n <= 1) return acc;
  return factorial(n - 1, n * acc);
}

function fibonacci(n, a = 0, b = 1) {
  if (n === 0) return a;
  if (n === 1) return b;
  return fibonacci(n - 1, b, a + b);
}

3.3 浏览器 TCO 支持

4. 蹦床函数

function trampoline(fn) {
  return function (...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

function factorialThunk(n, acc = 1) {
  if (n <= 1) return acc;
  return () => factorialThunk(n - 1, n * acc);
}

const factorial = trampoline(factorialThunk);
console.log(factorial(100000)); // 不会栈溢出