【思维风暴】算法迭代和递归的理解

雨点打透心脏的1/2处 2023-02-20 02:52 5阅读 0赞

### 文章目录 ###

*  递归与迭代
 *  递归消耗内存的缺点
 *  为什么要有迭代
 *  需要用迭代消解递归的情况
 *  不需要消解的递归
 *  结束语

# 递归与迭代 #

递归与迭代都是基于控制结构：迭代用重复结构，而递归用选择结构。递归与迭代都涉及重复：迭代显式使用重复结构，而递归通过重复函数调用实现重复。递归与迭代都涉及终止测试：迭代在循环条件失败时终止，递归在遇到基本情况时终止。使用计数器控制重复的迭代和递归都逐渐到达终止点：迭代一直修改计数器，直到计数器值使循环条件失败；递归不断产生最初问题的简化副本，直到达到基本情况。迭代和递归过程都可以无限进行：如果循环条件测试永远不变成false，则迭代发生无限循环；如果递归永远无法回推到基本情况，则发生无穷递归。

# 递归消耗内存的缺点 #

递归有许多缺点，它重复调用机制，因此重复函数调用的开销很大，将占用很长的处理器时间和大量的内存空间。每次递归调用都要生成函数的另一个副本(实际上只是函数变量的另一个副本)．从而消耗大量内存空间。迭代通常发生在函数内，因此没有重复调用函数和多余内存赋值的开销。那么，为什么选择递归呢？

# 为什么要有迭代 #

递归算法表示许多问题的求解方法时算法思想非常简洁。但是递归算法不仅时间效率非常差，而且由于递归算法是不断的函数调用和函数返回过程，因此其实际的计算机运行时间通常远大于循环方式算法的计算机运行时间，甚至在有限的时间内无法求解。这就存在一个把递归算法化为非递归算法的问题。

# 需要用迭代消解递归的情况 #

递归算法特别适合于所研究的问题或所处理的数据本身是递归定义的情况。然而，并不意味着这种递归定义保证递归算法是解决该问题的最好方法。事实上，主要是因为拿那种不合适的例子来解释递归算法概念，从而造成了对程序设计中使用递归的普遍怀疑和否定态度，并把递归同低效等同起来。而且在递归算法中，往往会因为追求代码短或者在求解问题时一味追求规律性，多用了无用的压栈和出栈的操作。比如用循环消解的尾递归，是多了无用的压栈和出栈才使速度受损的；斐波那契数列计算的递归改循环迭代所带来的速度大幅提升，是因为改掉了重复计算的毛病。假使一个递归过程中本身包含了大量冗余的操作，并且这个过程又可以用迭代来达到相同的效果。这时，我们就一般用迭代来消解递归。也就是说尾递归算法和单向递归算法可用迭代算法来代替。

# 不需要消解的递归 #

那种盲目的消解递归，不惜一切代价躲避递归，认为“递归的速度慢，为了提高速度，必须用栈或者其他的方法来消解”的说法是很片面的。如果一个递归过程用非递归的方法实现后，速度提高了，那只是因为递归做了一些无用功。假使一个递归过程必须要用栈才能消解，那么完全模拟后的结果根本就不会对速度有任何提升，只会减慢；如果你改完后速度提升了，那只证明你的递归函数写的有问题，如多了许多重复操作——打开关闭文件、连接断开数据库，而这些完全可以放到递归外面。可以在本质上是非递归的机器上实现递归过程这一事实本身就证明：为着实际目的，每一个递归程序都可以翻译成纯粹迭代的形式，但这包含着对递归栈的显式处理，而这些运算常常模糊了程序的本质，以致使它非常难以理解。  
因此，是递归的而不是迭代的算法应当表述成递归过程。如汉诺塔问题等。汉诺塔问题的递归算法中有两处递归调用，并且其中一处递归调用语句后还有其他语句，因此该递归算法不是尾递归或单向递归。要把这样的递归算法转化为非递归算法，并没有提高程序运行的速度，反而会使程序变得复杂难懂，这是不可取的。也就是说，很多递归算法并不容易改写成迭代程序：它们本质上是递归的，没有简单的迭代形式。这样的递归算法不宜转化为非递归算法。

# 结束语 #

说到底，在我们选择算法时应该全面分析算法的可行性、效率、代码优化。在综合了算法的各个因素后，选择合适的算法来编写程序，这样的程序才会达到优化的效果。