递归，可以让我们更敏锐更准确地抓住问题的要害，给出从形式上讲更简单的解决办法，因此它显得更加高明。然而从效率上来说，貌似复杂的迭代算法往往比递归效率更高。
如何设计一个数据结构算法？
减而治之
问题：计算n个整数之和。
迭代实现：
时间复杂度：O(n) 空间复杂度：O(2)
注：空间复杂度，默认是考量除了输入所需要的空间，实现算法所需要的用于计算的空间总量。因此这里是常数的空间复杂度。
分析上面的代码实现，这段代码的背后蕴含着某种典型算法的规律，如果把输入参数n看作问题的规模，每经过一次迭代，有一个数已经统计完毕，剩余的问题的规模就会递减一个元素，这种，通过逐步蚕食，不断缩减问题规模的策略，也就是减而治之的策略。
减而治之：遇到一个规模大的问题，将它分解为两个子问题，一个问题规模缩减，另一个问题化为平凡的子问题。继续缩减问题的规模，只到化为平凡问题。最后合并结果。
减而治之的递归实现：
时间复杂度：O(n)
分而治之：遇到一个规模大的问题，将它分解为两个规模相当的子问题，一步步地缩减子问题的规模，直到缩减为平凡问题，再把问题归并起来。这样的一种策略，就是分而治之的策略。
分而治之的递归实现：
分而治之实现版本
分而治之图解
时间复杂度分析
时间复杂度：O(n)
递推关系：
O(n) = 2 * O(n - 1) + 1; // 计算两个规模大致相等的问题+合并
O(1) = 1;
数组求和的问题过于简单，上述三种实现时间复杂度都为O(n)，无法体现减而治之分而治之的优势。
make it work, make it right, make it fast！
动态规划：通过递归找出算法的本质，并给出一个初步的解之后，再将之转化为等效的迭代的形式。
问题：求斐波那契数列第n项的值。
递归实现
时间复杂度：O(2^n) （实际是1.618...^n）
封底估算：
φ=(1+根号5) / 2 = 1.618...
φ^36 = 2^25；
φ^5 = 10;
10^9/s:主流计算机主频计算吞吐量
10^5 = 1 day；
10^10 = 300 year；
斐波那契的第43项：φ^43 = 2^30 = 10^9 = 1s; 能明显感觉到卡顿
斐波那契递归实现低效的根源在于：各递归实例均被大量地重复地调用。
那么，如何让每一项实例只被计算1次？
解决方法A(记忆：memoization)：将已计算过实例的结果制表备查
解决方法B(动态规划：dynamic programming)：颠倒计算方向，由自顶而下递归变为自底而上迭代。
图解
代码实现
利用两个向量，使它们始终指向相邻两阶。
时间复杂度：O(n)，空间复杂度O(2)
总结
递归：设计出可行且正确的解；
动态规划：消除重复计算与，提高效率。
网友评论