algorithm - 快速斐波那契递归

Question

我正在尝试记忆斐波那契递归的算法。以下内容:

public int fibonacci(int n)  {
  if(n == 0)
    return 0;
  else if(n == 1)
    return 1;
  else
    return fibonacci(n - 1) + fibonacci(n - 2);
}

不是我正在寻找的东西，因为它很贪婪。这将呈指数增长(看看 Java recursive Fibonacci sequence - 初始参数越大，将进行越多无用的调用)。

可能存在类似于“循环参数移位”的东西，其中调用先前的斐波那契值将检索值而不是再次计算它。

Answer 1

可能是这样的:

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

这个函数是尾递归的。这意味着它可以非常有效地优化和执行。事实上，它被优化为一个简单的循环..