3.1 递归的概念

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

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

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

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

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

下述代码给出了用非递归和递归的方法来输出n个自然数，从中可以看出递归与非递归思想的不同之处。对于递归方法，可以将其分为两个不同的阶段：递推与回归。其中，递推阶段主要负责把复杂的问题的求解分解为比原问题简单一些的问题的求解，而回归则指的是当获得最简单的情况后，逐步返回，依次得到复杂的解。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

例3.1 求解Fibonacci数列。

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

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

例3.2 汉诺塔（Hanoi）问题。

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

设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阶汉诺塔问题的算法，其中第一个参数表示问题的阶数，第2、3、4参数分别表示起始柱、中间柱与目的柱，过程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）实际上还是Hanoi塔问题，如果最原始的问题为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)。