当前位置：首页 > JavaScript

js递归实现

2026-04-06 23:41:45JavaScript

递归的基本概念

递归是一种通过函数调用自身来解决问题的方法。在JavaScript中，递归函数需要满足两个条件：基线条件（终止条件）和递归条件（调用自身）。

递归实现阶乘

阶乘是递归的经典案例。以下是一个计算阶乘的递归函数：

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

递归实现斐波那契数列

斐波那契数列是另一个常见递归示例。以下是实现代码：

js递归实现

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

递归遍历树形结构

递归非常适合处理树形结构数据。以下是一个遍历嵌套对象的示例：

function traverse(obj) {
  for (let key in obj) {
    if (typeof obj[key] === 'object') {
      traverse(obj[key]); // 递归处理子对象
    } else {
      console.log(key + ': ' + obj[key]);
    }
  }
}
const tree = {a:1, b:{c:2, d:{e:3}}};
traverse(tree);

递归实现数组扁平化

递归可以将多维数组扁平化为一维数组：

js递归实现

function flatten(arr) {
  let result = [];
  arr.forEach(item => {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item)); // 递归处理子数组
    } else {
      result.push(item);
    }
  });
  return result;
}
console.log(flatten([1, [2, [3, 4], 5]])); // 输出[1,2,3,4,5]

递归注意事项

递归可能导致堆栈溢出，特别是处理大规模数据时。尾递归优化可以缓解这个问题，但JavaScript引擎对尾调用的支持有限。

// 尾递归优化的阶乘实现
function factorial(n, total = 1) {
  if (n === 0) return total;
  return factorial(n - 1, n * total);
}
console.log(factorial(5)); // 输出120

递归与循环的比较

递归代码通常更简洁，但可能效率较低。对于性能敏感的场景，可以考虑用循环替代递归。例如斐波那契数列的循环实现：

function fibonacci(n) {
  let a = 0, b = 1, temp;
  for (let i = 0; i < n; i++) {
    temp = a;
    a = b;
    b = temp + b;
  }
  return a;
}
console.log(fibonacci(6)); // 输出8