如何用递归实现返回前N项斐波那契数列的数组？

你的代码问题出在两点：

1. 每次递归调用都会新建一个空数组array，无法累积之前计算出的数列项；
2. 最后返回的是array[n] = ...这个赋值表达式的结果（也就是当前项的数值），而非完整数组。

方法1：基于前序结果递归构建数组 #

这种思路从基础情况返回对应长度的数组，递归时先获取前n-1项的数组，再计算新项追加进去：

function fibRec(n) {
  // 基础情况：n=1返回仅包含0的数组
  if (n === 1) {
    return [0];
  }
  // n=2返回前两项数组
  if (n === 2) {
    return [0, 1];
  }
  // 先拿到前n-1项的数组
  const prevSequence = fibRec(n - 1);
  // 计算新项：数组最后两项的和
  const nextNum = prevSequence[prevSequence.length - 1] + prevSequence[prevSequence.length - 2];
  // 追加新项后返回完整数组
  prevSequence.push(nextNum);
  return prevSequence;
}

console.log(fibRec(10)); // 输出：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

这种方式的递归是线性复杂度的，因为每次只调用一次fibRec(n-1)，不会像你原代码那样重复计算子问题。

方法2：尾递归累积数组 #

如果想使用尾递归（部分JS引擎会优化尾递归避免栈溢出），可以通过参数传递当前已构建的数组：

function fibRec(n, currentSeq = [0, 1]) {
  if (n === 1) {
    return [0];
  }
  // 如果当前数组长度已经达到n，直接返回前n项
  if (currentSeq.length >= n) {
    return currentSeq.slice(0, n);
  }
  // 计算下一项并生成新数组，继续递归
  const nextNum = currentSeq[currentSeq.length - 1] + currentSeq[currentSeq.length - 2];
  return fibRec(n, [...currentSeq, nextNum]);
}

console.log(fibRec(10)); // 输出：[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

这个版本通过默认参数初始化前两项数组，每次递归都传入包含新项的数组，直到数组长度满足要求后返回结果。

内容的提问来源于stack exchange，提问作者user26935357