我试图回忆斐波纳契递归算法。 下列：
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的递归斐波那契序列 -越没用调用将进行更大的初始参数）。
有可能是像一个“循环论证转移”，其中调用以前的斐波那契值将检索值，而不是再次计算它的。
也许是这样的：
int fib(int term, int val = 1, int prev = 0)
{
if(term == 0) return prev;
return fib(term - 1, val+prev, val);
}
这个功能是尾递归。 这意味着它可以被优化，非常有效地执行。 事实上，它被优化成一个简单的循环..
这类问题是线性复发的类型和它们通过快速矩阵幂最快的解决。 这里的博文 ，描述这种方法简洁。
您可以通过使用递归做斐波那契的蛮快的版本记忆化 （：存储先前的结果，以避免重新计算它们的意思）。 例如，这里是在Python，其中一本字典用于保存先前的结果概念证明：
results = { 0:0, 1:1 }
def memofib(n):
if n not in results:
results[n] = memofib(n-1) + memofib(n-2)
return results[n]
它迅速返回通常会阻止“正常”的递归版本的输入值。 只要记住，一个int数据类型是不够举行大型的结果，并使用任意精度的整数建议。
不同的选项完全 - 改写这个迭代版本...
def iterfib(n):
a, b = 0, 1
for i in xrange(n):
a, b = b, a + b
return a
......作为一个尾递归函数，称为loop在我的代码：
def tailfib(n):
return loop(n, 0, 1)
def loop(i, a, b):
if i == 0:
return a
return loop(i-1, b, a+b)
我发现了一个关于Fibonacci问题的有趣的文章
这里的代码片段
# Returns F(n)
def fibonacci(n):
if n < 0:
raise ValueError("Negative arguments not implemented")
return _fib(n)[0]
# Returns a tuple (F(n), F(n+1))
def _fib(n):
if n == 0:
return (0, 1)
else:
a, b = _fib(n // 2)
c = a * (2 * b - a)
d = b * b + a * a
if n % 2 == 0:
return (c, d)
else:
return (d, c + d)
# added iterative version base on C# example
def iterFib(n):
a = 0
b = 1
i=31
while i>=0:
d = a * (b * 2 - a)
e = a * a + b * b
a = d
b = e
if ((n >> i) & 1) != 0:
c = a + b;
a = b
b = c
i=i-1
return a
假设你想拥有的第n个谎号码，然后构建包含前述号码数组
int a[n];
a[0] = 0;
a[1] =1;
a[i] = n[i-1]+n[n-2];
在JavaScript中使用递归和用于增加效率的延迟初始化缓存的例子：
var cache = {};
function fibonacciOf (n) {
if(n === 0) return 0;
if(n === 1) return 1;
var previous = cache[n-1] || fibonacciOf(n-1);
cache[n-1] = previous;
return previous + fibonacciOf(n-2);
};
duedl0r的算法转换为斯威夫特：
func fib(n: Int, previous: (Int, Int) = (0,1)) -> Int {
guard n > 0 else { return 0 }
if n == 1 { return previous.1 }
return fib(n - 1, previous: (previous.1, previous.0 + previous.1))
}
样例：
fib(4)
= fib(4, (0,1) )
= fib(3, (1,1) )
= fib(2, (1,2) )
= fib(1, (2,3) )
= 3
你需要以停止指数增长记住的计算值。
下面是使用内存更快递归的工作示例。
计算Fibonacci数
一个好的算法快速计算斐波那契数是（在python）：
def fib2(n):
# return (fib(n), fib(n-1))
if n == 0: return (0, 1)
if n == -1: return (1, -1)
k, r = divmod(n, 2) # n=2k+r
u_k, u_km1 = fib2(k)
u_k_s, u_km1_s = u_k**2, u_km1**2 # Can be improved by parallel calls
u_2kp1 = 4 * u_k_s - u_km1_s + (-2 if k%2 else 2)
u_2km1 = u_k_s + u_km1_s
u_2k = u_2kp1 - u_2km1
return (u_2kp1, u_2k) if r else (u_2k, u_2km1)
def fib(n):
k, r = divmod(n, 2) # n=2k+r
u_k, u_km1 = fib2(k)
return (2*u_k+u_km1)*(2*u_k-u_km1)+(-2 if k%2 else 2) if r else u_k*(u_k+2*u_km1)
如果你需要非常快的计算，链接到libgmp和使用mpz_fib_ui（）或mpz_fib2_ui（）函数。
