斐波那契数列的定义为 F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)。使用朴素递归方法计算 F(n)的时间复杂度是指数级的。而使用动态规划(或迭代)方法的时间复杂度是线性的。造成这种巨大差异的根本原因是?
递归函数调用栈开销过大
操作系统对递归深度有限制
朴素递归中存在大量的重叠子问题未被重复利用
动态规划使用了更少的数据存储空间