从递归到动态规划，fibonacci算法的优化

fibonacci是数学中一个经典的数列，现在我们考查这样一个问题，实现一个算法，计算fibonacci数列的第n项。如何实现这样一个数列呢。首先我们先回顾一下fibonacci数列的定义。

Fibonacci数列的定义如下：从n =1开始 f(1)= 1,f(2) = 1,从第三项开始，每一项都等于前两项之和。由此可得到较为简洁的数学公式描述如下：

$F(n)=n (若n≤1时)$

$F(n)=F(n-1)+F(n-2) (若n ≥2时)$

基于fibonacci的数学定义，首先可以想到利用二分递归的思路来做这一道题。因为第一F(n)有明确的递归公式，第二F(n)给出了递归的平凡情况，f(1),f(2) = 1。基于上述条件就可以很快写出fibonacci数列算法的二分递归版本如下：

可以看到这一个版本的算法就如同fibonacci的数学公式定义一样，非常简洁明了。这也是递归的魅力所在。从宏观上把握问题的实质，深层抽象算法过程中的主要矛盾和一般模式。并最终得到简洁优美且正确的算法。

但是递归的美丽背后也付出了代价。

首先，递归的空间量取决于递归的深度，针对同一个问题的算法，递归版本的往往需要耗费更多的空间。而且，就二分递归版的fibonacci算法而言，二分递归思想的本质可以概括为分而治之，F(n) = F(n-1)+F(n-2)，继续展开会发现。这其中存在着大量的重复计算。实际上，该版本的算法时间复杂度高达∂（2^n ）【感兴趣的同学可以尝试证明一下二分递归版本的时间复杂度，这里需要用到高中的复合函数的知识去构造辅助函数，基于篇幅我们不展开讨论】，而指数复杂度的算法，在实际生产应用中，往往是不可接受的。

我们既然发现在二分递归算法中存在大量的重复计算。那我们自然就能想到，利用一定量的辅助空间，在各子问题求解之后，记录下问题的答案。下次若还有计算该项的地方，直接从辅助空间中取值，避免重复的计算开销。

若从F(N)开始自顶而下计算，每次计算的时候都去检查该项是否已经计算过。我们称这一种算法思路为制表法，而从F(1)开始，自底而上计算，F(n-1)得出的时候，一定有F(n-2)和F(n-3)这两项的值。然后用F(n-1)与F(n-2)得到F(n)，这种思路也就是所谓的动态规划。

我们接下来给出这两种思路的算法实现。

由fibonacci数列的数学公式定义可以得出，F(N-1)和F(N-2)并非独立，在递归的时候，每次递归都保留对前一项的引用。当头递归到达递归基（递归的平凡情况）开始逐步得到计算结果并退出操作栈。

举例如下：计算F(N-1)=F(n-2)+F(N-3)时。保留对F(N-2)的引用。用于在计算F(N)=F(N-1)+F(N-2)的时候进行计算。该算法的递归深度正比于输入规模n，呈现线性递归，时间复杂度为∂(n)，一共出现∂(n)个递归实例，所以还需要∂(n)规模的附加空间。

理解了制表法的思路后，动态规划的思路也就好理解了。制表法采用的是头递归的方式，即到达了递归基以后再开始实际计算出每一项的值。

而动态规划采用了尾递归的方式。从F(1)开始就得出每一项的值，每次都保留对F(n-1)的值的计算结果用于下一次计算。动态规划法需要进行2n次的基本运算，实际时间复杂度也为∂(n),但是因为仅使用了两个中间变量f,g.所以只需要常数规模的空间既可完成计算。在空间复杂度上相比较制表法有了大幅的提高。

到这里，我们对于fibonacci数计算算法的优化也就到了尾声。回顾一下，我们可以发现我们优化算法的过程也是从问题中找问题，然后从问题中找答案，从答案中再找问题周而复始，一步步推进的。算法优化的思路是从复杂问题中抽象出变化的规律、观察出变化中平凡的情况，将大的问题分而治之，得到小的问题去解决的。这也可以指导我们的日常生活，多观察，多提问，多思考，多总结。这样才能不断优化自身，提高自己处理问题的水平。