专注于互联网--专注于架构

回溯与递归:递归与动态编程

　　前面我还刚刚在学习递归时拿Fibnoacci数列的递归实现做递归学习的例子呢，今天看到＜＜算法I-IV－基础，数据结构，排序与搜索＞＞的动态编程一节时，有这么一段话： 　　下面是一个Fibonacci数列的递推的直接递归实现。千万不要使用这样的程序，因为它极端低效。实际上，对于计算F(N)的递归调用的数目正是F(N+1),但是，F(N)大约是1.618的N次方，令人时移尴尬的事实是那个递归程序（见上一篇日志）是针对这个微不足道的计算的指数级算法。　 　　然后他给出了用数组实现的一个计算N个Fibonacci数的非递归程序，接着说实际只需跟踪2个值就可以了，因 [阅读全文] [PDF]