O(n) 中的递归斐波那契

Question

我想问为什么所有（至少我在搜索时看到的）递归斐波那契函数都是 2^n，为什么不尝试像下面这样在 O(n) 中工作的函数，它有什么缺点吗？:

let fib = (n, a=0, b=1) => {
  if(n>2){
    return fib(n-1, b, a+b);
  }
  return a+b;
};

console.log(fib(6,0,1));

我尝试寻找这样的功能，但没有找到。

Answer 1

您可以尝试使用尾递归：

function fib(term, int val = 1, int prev = 0)
{
 if(term == 0) return prev;
 return fib(term - 1, val+prev, val);
}