算法导论第三版新增27章中文版(5)

计算机科学与技术

FIB(n)

1 if n ≤ 1

2 return n

3 else x = FIB(n-1)

4 y = FIB(n-2)

5 return x+y

如果要计算很大的 Fibonacci 数，是不能使用该算法的，因为其中有大量的重复计算。图 27.1 展示了在计算 F6 时所创建的递归过程实例树。其中，对于对于 FIB(6) 的调用会递归地调用 FIB(5) 和 FIB(4) 。而对 FIB(5) 的调用又会去调用 FIB(4) 。这两个 FIB(4) 实例返回的结果完全相同（ F4 =3 ）。由于 FIB 并没有去记住这些结果，因此对于 FIB(4) 的第二次调用重复了第一次调用的工作。