下载掌阅APP，畅读海量书库
立即打开
递归是计算机科学中的一个重要概念，是程序设计中的一个强有力的方法，它使得程序设计和算法描述形式简洁且易于理解。在本书的后续章节中，一些重要算法都是采用递归方法实现的。
在现实生活中，有些问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的 问题完全相同 ，只是 在数量规模上不同 。
例如，一个人要搬走10块石头，怎么搬呢？他可以这样考虑，只要先搬走9块，那剩下的1块就能搬完了；然后考虑那9块怎么搬？只要先搬走8块，那剩下的一块就能搬完了……直到只剩下1块石头，直接搬走。
在这种情况下，递归的方法可以从思路上使许多问题的解决方法得以简化。
在数学上，有些概念的定义方式是递归的，即用一个概念本身直接或者间接地定义它自身。
例如，计算1～100的累加和，可以表示为：计算1～99的累加和，再加上100；1～99的累加和又可以表示为1～98的累加和，再加上99……以此类推。
再如，计算2 n ，可以演变为先计算2 n-1 ，再乘以2；而2 n-1 的计算又可演变为先计算2 n-2 ，再乘以2……直到计算2 0 =1。
这种定义方式体现了一种逻辑思想，同时又是一种解决问题的方案。递归定义的问题可以用递归算法来求解。
递归是一个过程或函数直接或间接调用自身的一种方法，它可以把一个大型的问题层层转化为一个与原问题相似、但规模较小的问题来求解。
递归是数学中一种非常重要的方法。
例如，数学中阶乘的定义，n的阶乘可以表示为
再如，斐波那契（Fibonacci）数列指的是这样一个数列：
1，1，2，3，5，8，13，21，34…
这个数列从第三项开始，每一项都等于前两项之和，数列的第n项Fib（n）可定义为
可以看出， 递归实质上也是一种循环结构，它把“较复杂”情况的计算归结为“较简单”情况的计算，一直归结到“最简单”情况的计算为止。
直接或间接调用自身的程序称为递归程序。
递归是一种特殊的嵌套调用，是某个函数调用自己，而不是调用另外一个函数。这是一种方法（函数）直接或者间接调用自身的编程技术。
有些问题采用循环的方法解决，执行的速度比递归方法快，但是为什么采用递归算法呢？这是因为递归概念上简化了问题，而不是因为它提高了效率。
在程序设计中，递归算法是一个强有力的工具。有很多问题不使用递归算法是很难解决的。当然，也有些递归问题可以转换成非递归问题求解。
1.递归算法的构成
在数值计算领域可以采用递归算法，在非数值领域递归的应用也非常广泛。可以说，递归算法就是程序设计中的数学归纳法。
一般来说， 能够用递归算法解决的问题应该满足以下三个条件。
1）需要解决的问题可以化为一个或多个子问题来求解，而这些子问题的求解方法与原来的问题完全相同，只是在数量规模上不同。
2）递归调用的次数必须是有限的。
3）必须有结束递归的条件（边界条件）来终止递归。
例如，在第1.5.1小节提到的计算n的阶乘的数学公式中，求n的阶乘被转化为求（n-1）的阶乘，仍然是计算阶乘的问题，但问题的规模由n变成了（n-1）。在计算n的阶乘的过程中，会递归调用自身多次：n！，（n-1）！，…，1！，0！。但调用次数是有限的，递归结束的条件是0！的值为1。
一般， 递归算法的设计一般分为两步。
1）将规模较大的原问题分解为一个或多个规模较小的而又类似于原问题特性的子问题，即将较大的问题递归地用较小的子问题来描述，解原问题的方法同样可以用来解决子问题。
2）确定一个或多个不需要分解、可直接求解的最小子问题。
第1）步是递归的步骤，第2）步中的最小子问题是递归的终结条件。
根据n！的定义，可以很自然地写出相应的递归函数。
【例1-7】计算n！的递归方法。
递归函数都有一个递归的终结条件，在本例中，当n等于0时，将不再继续递归。递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数而已。
【例1-8】计算斐波那契（Fibonacci）数列第n项的递归方法。
递归的方法只需少量的程序代码就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
2.递归调用的内部过程
递归函数的调用类似于多层函数的嵌套调用，只是调用单位和被调用单位是同一个函数而已。对于例1-7中求阶乘的问题，假设程序运行时，输入4，那么程序的执行过程如图1-4所示。
图1-4 例1-7中n=4时程序的执行过程
可以看出， 递归调用的过程分为两个阶段。
1）递归过程：将原始问题不断转化为规模小一级的新问题，从求4！变成求3！，变成求2！，最终达到递归终结条件，求1！。
2）回溯过程：从已知条件出发，沿递归的逆过程，逐一求值返回，直至递归初始处，完成递归调用。
在这两个阶段中，系统会分别完成一系列的操作。 在递归调用之前，系统需完成以下三件事。
1）为被调用过程的局部变量分配存储区。
2）将所有的实参、返回地址等信息传递给被调用过程保存。
3）将控制转移到被调过程的入口。
从被调用过程返回调用过程之前，系统也应完成三件工作。
1）保存被调过程的计算结果。
2）释放被调过程的数据区。
3）依照被调过程保存的返回地址将控制转移到调用过程。
在计算机中，是通过使用系统栈（后面的章节会介绍“栈”）来完成上述操作的。
递归算法解决问题的方式和特点： 将初始问题转化为解决方法相同的新问题，而新问题的规模要比原始问题小，新问题又可以转化为规模更小的问题，直至最终归结到最基本的情况（可以简单解决的问题）——递归的终结条件。
递归方法有许多不利之处，例如， 递归调用会占用大量的内存和消耗大量的时间 ，造成执行效率低。但有时 采用递归方法编写的程序简洁、清晰，可读性好 。递归方法成为有些问题的最佳解决方法，典型的应用除了例1-7求n！和例1-8计算斐波那契数列，以及将要在第1.5.4小节介绍的汉诺塔问题外，还有后续章节中的二叉树的遍历、图的遍历、二分查找、快速排序和归并排序等。
有些递归问题可以转化为采用非递归的方法实现，例如，伪递归可以用递推的方法实现，有些递归的问题可以用回溯法解决。
1.递归转换为递推
当递归算法所涉及的数据定义形式是递归的情况下，通常可以将递归算法转换为递推算法，用递归的边界条件作为递推的边界条件。例如，求阶乘、斐波那契数列等。
递推也是一种从已知条件出发，用一种具体的算法，一步一步接近未知，一般采用循环结构，经常和枚举配合使用。递推算法在求解的过程中，每一个中间量都是已知的，而且没有重复计算，运算简洁，但是书写代码和理解代码比较难。
求阶乘及斐波那契数列某项的递推算法如例1-9、例1-10所示。
【例1-9】阶乘的递推算法。
【例1-10】斐波那契数列的递推算法。
递归是从未知到已知，再从已知返回未知，利用子问题与父问题的关系，进而构造成有递归性的函数。而递推与此相反，从已知到未知。类似于一般解数学题的思路，从未知与已知的顺序上来看，它们好像是互逆过程，其实不然。递归把问题简单化，抓的是问题与子问题的联系；而递推是把中间解推进，抓的是中间量与更靠近未知的中间量的联系。两者是不同的，不能简单地看成是互逆过程。
2.递归转换为回溯
回溯算法的步骤如下：
1）定义一个解空间，它包含问题的解。
2）用适于搜索的方式组织该空间。
3）用深度优先法搜索该空间，利用限界函数避免移动到不可能产生解的子空间。
回溯算法的一个有趣的特性是在搜索执行的同时产生解空间。在搜索期间的任何时刻，仅保留从开始节点到当前节点的路径。因此，回溯算法的空间需求为O（从开始节点起最长路径的长度）。这个特性非常重要，因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话，再多的空间也不够用。
递归算法简单直观，是整个计算机算法和程序设计领域中一个非常重要的方面，必须熟练掌握并能应用它。递归算法在计算机中的执行过程比较复杂，需要用系统栈进行频繁的进出栈操作和转移操作。递归转化为非递归后，可以解决一些空间上不够的问题，但程序太复杂。所以，并不是一切递归问题都要设计成非递归算法。实际上，很多稍微复杂一点的问题（如汉诺塔问题、二叉树的遍历、图的遍历、快速排序等），不仅很难写出它们的非递归过程，而且即使写出来也非常累赘和难懂。在这种情况下，编写递归算法是最佳选择。
汉诺塔问题可简要描述如下：有a、b、c三个底座，上面可以放盘子，如图1-5所示。初始a底座上有n个盘子，这些盘子大小各不相同，大盘子在下，小盘子在上，依次排列。要求将a底座上的n个盘子移至c底座上，每次只能移动一个，并要求移动过程中保持小盘子在上大盘子在下，可借助b底座实现移动。编写程序输出移动步骤。
图1-5 汉诺塔问题
这个问题可用递归思想来分析，将n个盘子由a底座移动到c底座可分为如下三个过程。
1）先将a底座上n-1个盘子借助c底座移至b底座。
2）再将a底座上最下面一个盘子移至c底座。
3）最后将b底座上n-1个盘子借助a底座移至c底座。
上述过程是把移动n个盘子的问题转化为移动n-1个盘子的问题，按这种思路，再将移动n-1个盘子的问题转化为移动n-2个盘子的问题，直至移动1个盘子。
可以用两个函数来描述上述移动过程。
1）从一个底座上移动n个盘子到另一底座。
2）从一个底座上移动1个盘子到另一底座。
【例1-11】采用递归的方法解决汉诺塔问题。
程序运行时，假设输入4，那么程序运行结果如下。
