当前位置：首页 > JavaScript

js实现简单递归

2026-03-16 04:02:45JavaScript

递归的基本概念

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

实现阶乘的递归函数

阶乘是一个经典的递归示例，n的阶乘（n!）定义为n乘以(n-1)的阶乘，直到1。

function factorial(n) {
  if (n === 1) { // 基线条件
    return 1;
  }
  return n * factorial(n - 1); // 递归调用
}
console.log(factorial(5)); // 输出: 120

实现斐波那契数列的递归函数

斐波那契数列是另一个常见的递归示例，每个数字是前两个数字的和。

function fibonacci(n) {
  if (n <= 1) { // 基线条件
    return n;
  }
  return fibonacci(n - 1) + fibonacci(n - 2); // 递归调用
}
console.log(fibonacci(6)); // 输出: 8

递归遍历树结构

递归常用于遍历树形结构，例如DOM树或嵌套的对象。

function traverseTree(node) {
  console.log(node.value); // 处理当前节点
  if (node.children) { // 检查是否有子节点
    node.children.forEach(child => {
      traverseTree(child); // 递归处理子节点
    });
  }
}

const tree = {
  value: 'A',
  children: [
    { value: 'B', children: [] },
    { value: 'C', children: [
      { value: 'D', children: [] }
    ]}
  ]
};
traverseTree(tree); // 输出: A, B, C, D

递归的注意事项

递归可能导致栈溢出，尤其是当递归深度过大时。尾递归优化可以缓解这个问题，但JavaScript引擎对尾递归的支持有限。

// 尾递归优化的阶乘函数
function factorialTail(n, accumulator = 1) {
  if (n === 1) {
    return accumulator;
  }
  return factorialTail(n - 1, n * accumulator); // 尾递归调用
}
console.log(factorialTail(5)); // 输出: 120

递归与循环的对比

递归代码通常更简洁，但可能不如循环高效。某些问题（如树遍历）更适合递归，而其他问题（如简单迭代）可能更适合循环。

js实现简单递归

// 使用循环实现阶乘
function factorialLoop(n) {
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}
console.log(factorialLoop(5)); // 输出: 120