迭代、递归、动态规划的粗浅区别

简单说说个人对这三个概念的粗浅认识

递归可以说是最容易理解的一个概念 ,简单的说就是函数里面调用自己,问题转化为小问题,分而治之。

迭代的理解 就是通过上一步的结果,通过一个函数,得到现在的结果;而现在的结果,用同样的函数,得到再下一步的结果;不断迭代,简单举一个累加过程的例子, \( sum_{new} = sum_ {old} + arr[i] \) 。

或者从数学中很有名的牛顿迭代法来理解,之所以叫做迭代就是由于牛顿迭代法求根的时候,有一个迭代公式

\(x_{new} = x_{old} – \frac{f'(x_ {old} )}{f(x_ {old} )}\)

就是符合迭代的一个思想,就是用上一步的结果推下一步的结果, 而且每一步都是相同的公式, 不断迭代,直到逼近零点。

动态规划有点类似于迭代的方式,但是又不完全等同于迭代,因为动态规划是一种自底向上的一个算法,并且有自己的状态转移方程和最优子结构性质,转移方程有点类似于迭代法中的迭代公式。

发表评论

电子邮件地址不会被公开。 必填项已用*标注