3.1 递归的概念

递归是“函数调用自己”，这是对递归很浅的一种认识。斐波那契（Fibonacci）数列应该是最基础的递归数列了。关于递归，维基百科给出的定义是：

递归：在数学和计算机科学中，递归指由一种（或多种）简单的基本情况定义的一类对象或方法，并规定其他所有情况都能被还原为其基本情况。

递归使用的就是分治的思想，它是分治思想的一种具体实现，它们都是倾向于将问题化简，直到化简到某一个终结条件后，再层层向上追溯。因此，在使用递归时，必须有一个明确的递归结束条件，称为递归出口。通过上面的定义可以看出对于各类递归问题，都可以分成两个阶段，分别是：

1）递推：把复杂的问题的求解分解为比原问题简单一些的问题的求解；

2）回归：当获得最简单问题的解后，逐步返回，依次得到复杂问题的解。

下述代码给出了用非递归和递归的方法来输出n个自然数，从中可以看出递归与非递归思想的不同之处。

总的来说，递归一般可以用于解决以下三大类问题：

1）数据是按递归方式定义的。例如Fibonacci数列等。

2）问题解法可以按递归方式实现。例如回溯等。

3）数据的结构形式是按递归定义的。例如树的遍历、图的搜索等。

递归调用应用非常广泛，而且也易于理解，但在使用递归时，一般有如下几点内容需要注意：

1）终止条件：当递归函数符合这个限制条件时，它便不再调用自身。

2）不断推进：每一次递归，都要使问题朝着终止条件前进，否则是无法结束递归的。

3）设计法则：假设所有的递归调用都能运行。

4）合成效益法则：在不同的递归调用中解决同一个问题，不应该做重复性的工作。

用递归方法解决问题的过程中，递归函数的内部执行过程大致可以分为三步：

1）运行开始时，为递归调用建立一个工作栈，其结构包括实参、局部变量和返回地址；

2）每次执行递归调用之前，把递归函数的实参和局部变量的当前值以及调用后的返回地址压栈；

3）每次递归调用结束后，将栈顶元素出栈，使相应的实参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。

可以看出用递归方式解决问题的思路简单清晰，如果能够找出问题蕴含的递归结构，将很快得到结果，但是递归将导致执行过程中出现多次函数调用，使用到大量堆、栈空间，降低算法效率，费时费内存。递归常用场景有：阶乘、斐波那契数列、汉诺塔问题、整数划分、枚举排列及二叉树、图的搜索相关问题。下面将介绍几个用递归思想解决的经典问题。

例3.1 求解Fibonacci数列。

无穷数列<1,1,2,3,5,8,13,21,34,55,…>被称为Fibonacci数列。它可以递归定义为：

从这个定义可以看出F(n)的递归定义中，前两行为该递归函数的边界条件（递归出口），第三行为该递归函数的递归方程。由此可以很容易用递归的方法求出数列中第n个元素对应的取值。具体算法代码如下所示。

例3.2 汉诺塔问题。

上面的古老传说抽象为汉诺塔问题后，其定义为：

设A、B、C是3个塔座，初始时，在塔A上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n，现要求将塔座A上的这一叠圆盘移到塔座B上，并仍按同样顺序叠置。

在移动圆盘时应遵守以下移动规则：

1）每次只能移动1个圆盘；

2）任何时刻都不允许将较大的圆盘压在较小的圆盘之上；

3）在满足移动规则1和2的前提下，可将圆盘移至A、B、C中任一塔座上。

塔座上有n个圆盘的汉诺塔问题被称为n阶汉诺塔问题。现令过程Hanoi（n，a，c，b）表示解n阶汉诺塔问题的算法，其中第一个参数表示问题的阶数，第二、三、四个参数分别表示起始柱、中间柱与目的柱，过程MOVE（a，n，b）表示将起始柱A上编号为n的圆盘（最后一个圆盘）移动到目的柱B上。现在用递归的思路，可以用以下方法解决这个问题：

1）当n=1时，只要将编号1的盘子从A移到B即可。

2）当n>1时，要以C为辅助，此时设法将n-1个较小的盘子从A移到C，将剩下的最大盘子从A移到B，最后，再设法将n-1个较小的盘子从C移到B。这样，n个盘子的移动就可以分解为两次n-1个盘子的移动。

从上面的方法可知，要完成Hanoi（n，a，c，b）的工作，可以分解成四个步骤：

1）如果n=1，可直接将这一个圆盘移动到目的柱上，过程结束。如果n>1，则进行步骤2。

2）设法将起始柱的上面n-1个圆盘（编号1～n-1）按移动原则移动到中间柱上。

3）将起始柱上的最后一个圆盘（编号为n）移到目的柱上。

4）设法将中间柱上的n-1个圆盘按移动原则移到目的柱上。

由此可以看出，步骤2与步骤4实际上还是汉诺塔问题，如果最原始的问题为n阶汉诺塔问题，且表示为Hanoi( n, a, c, b )，则步骤2与步骤4为n-1阶汉诺塔问题，分别表示为：Hanoi( n-1, a, b, c )和Hanoi( n-1, c, a, b )。那么我们现在很容易给出解n阶汉诺塔问题的算法，代码如下所示。

递归算法代码简洁、清晰、易于验证，但时间与空间消耗较大，因为它有嵌套函数调用，如果调用层数太深，会存在堆栈溢出的风险。而迭代的形式则相对复杂，但效率较高。往往有这样的观点：能不用递归就不用递归，递归都可以用迭代来代替。从理论上讲，递归和迭代在时间复杂度方面是等价的（在不考虑函数调用开销和函数调用产生的堆栈开销情况下），但实际上递归确实效率比迭代低。迭代是利用变量的原值推算出变量的一个新值，它是一个从前向后归纳推演的过程，通过前面的过程函数不停地调用后面的过程函数解决问题，而递归却是一个从后向前再向后的推演过程，即自己调用自己。既然这样，递归没有任何优势，是不是就没有使用递归的必要了？那递归的存在有何意义呢？从算法结构来说，递归声明的结构并不总能够转换为迭代结构，原因在于结构的引申本身属于递归的概念，用迭代的方法在设计初期根本无法实现，因此在结构设计时，通常采用递归的方式而不是采用迭代的方式。一个极典型的例子就是链表，使用递归定义它极其简单，但是用非递归的方式去对其进行定义及调用处理说明就比较困难，因为这些问题的底层数据结构本身就是递归，尤其是在遇到环链、图、网格等问题时，使用迭代方式从描述到实现上都会变得不现实。

所以，对于上述求Fibonacci数列的问题，除了递归以外，使用迭代的方法也是可行的，而且效率更高。可以将已经计算过的数字缓存起来，下次计算的时候不需要再进行重复运算，从而可以大量节省运算时间。根据以上思路，示例代码如下所示。通过分析可知，这种方法的时间复杂度为O(n)。