JavaScript 中具有序列数组输出的斐波那契递归函数

Question

你好，我试图想出一个函数来返回斐波那契序列，这是一个数组，而不是通常的最后一个斐波那契数。

function fib(n,arr=[0]) {
  if (n===0||n===1) {
    arr.push(n)
    return arr;
  }
  let arr2 = fib(n-2);
  let arr1 = fib(n-1);
  arr1.push(arr2[arr2.length-1]+arr1[arr1.length-1]);
  return arr1;
}

它工作正常，但我对这里的硬编码 arr=[0] 不满意。我尝试将 arr=[] 改为，但最终我的序列排除了数组中本应存在的前 0 个条目。

我确信有更好的方法来解决这个问题。

PS：我想使用递归方法来解决这个问题，我知道它的指数时间复杂度很差，但我只是想练习我的递归编程技能。

Answer 1

  let arr2 = fib(n-2);
  let arr1 = fib(n-1);

您为每一步构建两个数组，因此您构建了 n! 数组...而不是只使用一个递归调用，例如：

 function fibonacci(n){
   if(n <= 2)
      return [0, 1].slice(0, n);
   const res = fibonacci(n - 1);
   res.push(res[res.length - 1] + res[res.length - 2])
   return res;
 }

但你真的需要递归吗？：

 function fibonacci(n){
   const arr = [0, 1].slice(0 , n);
   for(let i = 2; i < n; i++)
     arr[i] = arr[i - 1] + arr[i - 2];
   return arr;
 }