3.14 递归与迭代

前面几节介绍了两个可以方便地用递归与迭代实现的函数。本节要比较递归与迭代方法，介绍为什么程序员在不同情况下选择不同方法。

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

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

软件工程视点3.14

任何能用递归解决的问题也能用迭代(非递归)方法解决。递归方法优于迭代方法之处在于能更自然地反映问题，使程序更容易理解和调试。选择递归方法的另一个原因是可能没有明显的迭代方案。

性能提示3.7

在要求性能的情况下不要用递归方法。递归调用既花时间又占用更多的内存。

常见编程错误3．24

让非递归函数直接或通过另一函数间接调用自己是个逻辑错误。

大多数有关编程的教材都把递归放在后面再讲。我们认为递归问题比较复杂而且内容丰富，应放在前面介绍，本书余下部分会通过更多例子加以说明。图3.17总结了本书使用递归算法的例子和练习。

下面重新考虑书中重复强调的一些观点。良好的软件工程很重要，高性能也很重要，但是，这些目标常常是互相矛盾的。良好的软件工程是使开发的大型复杂的软件系统更容易管理的关键，面高性能是今后在硬件上增加计算需求时实现系统的关键，这两个方面如何取得折衷?

软件工程视点3.15

让程序以整齐有序的层次方式工作能提高软件工程质量，但这是有代价的。

性能提示1.8

功能化的程序(而不是没有函数的一个整体的程序)造成更多的函数调用，需要占用执行时间和计算机处理器空间。但作为一个整体的程序难以编程、测试、调试、维护和改进。

因此要使程序合理地功能化，应该一直保持性能与良好的软件工程之间的平衡。

图 3.17  本书使用递归算法的例子和练习