递归和迭代

/ algorithm / 没有评论 / 61浏览

递归和迭代

递归和迭代都是循环中的一种。

递归是重复调用函数自身实现循环。

迭代是函数内某段代码实现循环。

与普通循环的区别

  1. 迭代与普通循环的区别是:循环代码中参与运算的变量同时是保存结果的变量,当前保存的结果作为下一次循环计算的初始值。迭代使用计数器结束循环

  2. 递归循环中,遇到满足终止条件的情况时逐层返回来结束。

递归需要注意的

  1. 递归就是在过程或函数里面调用自身.
  2. 在使用递归时,必须有一个明确的递归结束条件,称为递归出口.

递归的两个阶段

  1. 递推:把复杂的问题的求解推到比原问题简单一些的问题的求解.
  2. 回归:当获得最简单的情况后,逐步返回,依次得到复杂的解.

空间利用率对比

递归和迭代的空间利用率

迭代是逐渐逼近,用新值覆盖旧值,直到满足条件后结束,不保存中间值,空间利用率高。

递归是将一个问题分解为若干相对小一点的问题,遇到递归出口再原路返回,因此必须保存相关的中间值,这些中间值压入栈保存,问题规模较大时会占用大量内存。

两者之间的关系

  1. 递归中一定有迭代,但是迭代中不一定有递归,大部分可以相互转换。
  2. 能用迭代的不用递归,递归调用函数,计算有重复,浪费空间,并且递归太深容易造成堆栈的溢出.