1.4.3 循环与递归的比较

循环与递归都是实现重复计算的机制，那么，它们之间的区别和联系有哪些？在遇到具体问题时，如何选择？在实际应用中，有很多问题的数学模型本身就是递归的，用递归来描述它们不仅非常自然而且证明算法的正确性也相对容易。每个迭代算法原则上都可以转换成与之等价的递归算法；反之则不然，也就是说不是每个递归算法都可以转换成与之等价的循环结构算法。下面举两个例子来对两种设计机制进行比较。

【例1-6】 任意给定十进制数：①从低位到高位逐位输出各位数字；②从高位到低位逐位输出各位数字。

问题分析

这是一个较为简单的问题，我们将从实现的角度来比较循环与递归对于问题的适应性。

计算模型

算法实现

在例1-6中，问题虽然改变了，但是对于递归的扰动非常小，而对于循环的扰动却很大。这一现象向我们展示了递归算法对于问题的适应性是非常强的。

【例1-7】 从n个自然数（1，2，3，…，n）中取出r个数的所有组合。

问题分析

排列组合是数学上的经典问题，从n个自然数中取出r个数的组合共有个。把这些组合全部列出来，要么是从小到大，要么是从大到小。例如，从5个数中取出3个数的所有组合如下。

（1）循环算法设计思想

若r是固定的，如r=3，循环设计较为简单，只需选取上述两种次序中的一种，给对应位置安插相应的值，用三重循环即可实现。

（2）递归算法设计思想

按递归算法设计要点，若是按从大到小的顺序找到组合序列，首先固定第一个数字n，那么问题就变为从剩下n-1个数里选择r-1个数，然后，再固定第二个数字为n-1，那么问题就变为从剩下n-2个数里选择r-2个数，依此类推，当够r个元素时，便得到一组解；这时，可以从未选择到的元素中选择另一个元素去替换最后一个元素（第r个元素），则可以得到第二组解，当剩余集合中再没有可选择元素（第r个元素为1）时，变换最后一个元素的组合完毕。接下来更换倒数第二个元素，重复上面的选择。当到达第一个数字n时，为一轮循环选择完毕，更换第一个数字为n-1，进入下一轮。每进行一轮选择，待选择元素都会减少。递归结束条件是第r个元素为1。

计算模型

（1）循环算法

设i代表第i个位置，则r个位置上的取值范围依次为：

其中，1≤r≤n，且r在循环算法实现时代表循环嵌套的层数，必须是定值。

（2）递归算法

由分析可得如下组合规律：

第1个数固定为n，需要求解；第2个数固定为n-1，需要求解；……；求解。

第1个数固定为n-1，需要求解；第2个数固定为n-2，需要求解；……；求解。

……

第1个数固定为r，需要求解。

若把每更换一次第1个数看成一次大的集合划分，由组合规律可知，共有n-r+1个大的集合，划分到第n-r+1次时，得到最后一个组合：r，r-1，…，1，这种划分称为纵向划分。每个大集合里，又可以看成一个较小集合纵向划分，小、大集合纵向划分的规律相同，只是小的纵向划分是待选元素集合与选择元素数量都要缩减，因此，最终会减少为“1中选1”。

综上所述，可得递归式为：

其中，等式右边括号中第1个成员代表组合中首个元素，第2个成员代表剩余组合方案。式（1-16）为递归结束条件，式（1-17）为递推公式。

算法设计与描述

算法分析

（1）循环算法

通过算法设计与描述可知，它由r(=3)来控制循环层数，每一层循环控制变量的取值范围都受上一层循环控制变量的限制，由此可得下式：

其中，1代表主体运算，即输出一组组合数。由式（1-18）可得：

因为r=3，依式（1-19）可得：

（2）递归算法

对于递归算法的分析，将在第2章中介绍，但是由计算模型不难看出，算法主体运算次数为：

当r=3时，有与式（1-20）相同。

这是一个经典的组合问题，在两种算法的主体部分，均没有任何多余的运算，因此，组合公式基本可以反映计算次数，通过上述分析也证明了这一点。但是，循环算法的“致命”弱点是r为定值，即循环的嵌套层次是不能改变的，而递归算法r可以是任意小于n的值。对比循环算法，递归算法强大的设计能力体现无疑。但是，递归算法在实现运行时，用到了大量的入栈出栈，实际执行效率并不高。

算法实现

在例1-7中，递归算法的主体代码量与循环算法差不多，而多数情况下，递归要比循环代码少，如数据结构中的二叉树的三种遍历方式等。通过上述两个例子，可以对比得到表1-2所示内容。

尽管递归设计机制功能强大，但并不意味着它就是高效地最适应求解某个具体问题。通常衡量一个算法的优劣，还在于它应用的场景及问题，在后面的研究中，大家会逐渐地认识到这一点。