js 实现递归

递归的基本概念

递归是一种函数调用自身的技术，通常用于解决可以被分解为相似子问题的问题。在 JavaScript 中，递归函数需要包含一个基线条件（终止条件）和递归条件（调用自身的条件）。

递归的实现步骤

定义一个递归函数时，需要明确基线条件和递归条件。基线条件用于终止递归，避免无限循环；递归条件用于继续调用函数自身。

function factorial(n) {
  if (n === 0 || n === 1) { // 基线条件
    return 1;
  } else { // 递归条件
    return n * factorial(n - 1);
  }
}

递归的常见应用

递归常用于解决数学问题（如阶乘、斐波那契数列）、遍历数据结构（如树、链表）等。

function fibonacci(n) {
  if (n <= 1) { // 基线条件
    return n;
  } else { // 递归条件
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

递归的优化

递归可能导致堆栈溢出或性能问题，尤其是对于深度较大的递归调用。尾递归优化或改用循环（迭代）可以改善性能。

function factorialTailRecursive(n, accumulator = 1) {
  if (n === 0) { // 基线条件
    return accumulator;
  } else { // 尾递归调用
    return factorialTailRecursive(n - 1, n * accumulator);
  }
}

递归的注意事项

递归函数必须确保最终会触发基线条件，否则会导致无限递归和堆栈溢出。递归深度受限于 JavaScript 引擎的调用堆栈限制。

// 错误的递归示例（缺少基线条件）
function infiniteRecursion() {
  return infiniteRecursion(); // 无限递归
}

递归与迭代的对比

递归代码通常更简洁，但可能不如迭代高效。对于性能要求高的场景，可以考虑将递归改写为循环。

// 阶乘的迭代实现
function factorialIterative(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}