斐波那契数列

斐波那契数列是指一个数列，其中每个下一项是前两项之和。 斐波那契数列中的每个数字都称为斐波那契数。

示例: 0 ,1,1,2,3,5,8,13,21,....................... 是一个斐波那契数列。

斐波那契数 F_n 定义如下

F0 = 0
Fn=1
Fn=F(n-1)+ F(n-2)

FIB (n) 
 1. If (n < 2) 
 2. then return n 
 3. else return FIB (n - 1) + FIB (n - 2)

图：显示了调用 fib (8) 的四个递归级别

图：计算斐波那契数期间的递归调用

对 fib (n) 的单个递归调用会导致一次对 fib (n - 1) 的递归调用，两次对 fib (n - 2) 的递归调用，三次对 fib (n - 3) 的递归调用，五次对 fib (n - 4) 的递归调用，通常，Fk-1 对 fib (n - k) 的递归调用。 我们可以通过写下递归调用的结论并在以后需要时再次查找它们来避免这种不必要的重复。 这个过程称为记忆化。

这是带有记忆化的算法

MEMOFIB (n)
 1 if (n < 2) 
 2 then return n
 3 if (F[n] is undefined)
 4 then F[n] ← MEMOFIB (n - 1) + MEMOFIB (n - 2)
 5 return F[n]

如果我们跟踪对 MEMOFIB 的递归调用，我们会发现数组 F [] 从下到上填充。 也就是说，首先是 F [2]，然后是 F [3]，依此类推，直到 F[n]。 我们可以用一个简单的 for 循环代替递归，该循环仅按该顺序填充数组 F []

ITERFIB (n) 
 1 F [0] ← 0 
 2 F [1] ← 1 
 3 for i ← 2 to n 
 4 do 
 5 F[i] ← F [i - 1] + F [i - 2] 
 6 return F[n]

该算法显然只需要 O (n) 时间来计算 Fn。 相比之下，原始递归算法需要 O (∅^n;),∅ = = 1.618。 ITERFIB 比原始递归算法实现了指数加速。