快速斐波那契递归 [英] Fast Fibonacci recursion
问题描述
我试图回忆起在斐波那契递归算法。以下内容:
I'm trying to recall an algorithm on Fibonacci recursion. The following:
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的递归Fibonacci序列 - 越大的初始参数更没用的电话将进行)。
is not what I'm looking for because it's greedy. This will grow exponentially (just look at Java recursive Fibonacci sequence - the bigger the initial argument the more useless calls will be made).
有可能是有点像循环论证移位,其中调用previous斐波那契价值将再次检索计算它的价值吧。
There is probably something like a "cyclic argument shift", where calling previous Fibonacci value will retrieve value instead of calculating it again.
推荐答案
也许是这样的:
int fib(int term, int val = 1, int prev = 0)
{
if(term == 0) return prev;
if(term == 1) return val;
return fib(term - 1, val+prev, val);
}
此功能是尾递归。这意味着它可以优化和执行非常有效。事实上,它被优化成一个简单的循环。
this function is tail recursive. this means it could be optimized and executed very efficiently. In fact, it gets optimized into a simple loop..
这篇关于快速斐波那契递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!