3.3.1 递归的定义
递归是指在函数的定义中，在定义自己的同时又出现了对自身的调用。如果一个函数在函数体中直接调用自己，称为直接递归调用。如果经过一系列的中间调用，间接调用自己的函数称为间接递归调用。
1.递归函数
例如，n的阶乘递归定义如下：
n的阶乘算法如下：
Ackermann函数定义如下：
Ackerman函数相应算法如下：
2.递归调用过程
递归问题可以分解成规模小且性质相同的问题加以解决。下面以著名的汉诺塔问题为例来说明递归调用的过程。
n阶汉诺塔问题。假设有三个塔座X、Y、Z，在塔座X上放置有n个直径大小各不相同、从小到大编号为1，2，…，n的圆盘，如图3.10所示。要求将X轴上的n个圆盘移动到塔座Z上并要求按照同样的叠放顺序排列，圆盘移动时必须遵循以下规则：
（1）每次只能移动一个圆盘。
图3.10 3阶汉诺塔的初始状态
（2）圆盘可以放置在X、Y和Z中的任何一个塔座。
（3）任何时候都不能将一个较大的圆盘放在较小的圆盘上。
如何实现将放在X上的圆盘按照规则移动到Z上呢？当n=1时，问题比较简单，直接将编号为1的圆盘从塔座X移动到Z上即可。当n>1时，需要利用塔座Y作为辅助塔座，如果能将放置在编号为n之上的n-1个圆盘从塔座X移动到Y上，则可以先将编号为n的圆盘从塔座X移动到Z上，然后将塔座Y上的n-1个圆盘移动到塔座Z上。而如何将n-1个圆盘从一个塔座移动到另一个塔座又成为与原问题类似的问题，只是规模减小了1，因此可以用同样的方法解决。这是一个递归的问题，汉诺塔的算法描述如下。
下面以n=3为例来说明汉诺塔的递归调用过程。如图3.11所示。当n>1，经历3个过程移动圆盘。
第1个过程，将编号为1和2的圆盘从塔座X移动到Y。
第2个过程，将编号为3的圆盘从塔座X移动到Z。
第3个过程，将编号为1和2的圆盘从塔座Y移动到Z。
图3.11 汉诺塔递归调用过程
第1个过程，通过调用Hanoi（2,x,z,y）实现。Hanoi（2,x,z,y）又调用自己，完成将编号为1的圆盘从塔座X移动到Z，如图3.12所示。将编号为2的圆盘从塔座X移动到Y，编号为1的圆盘从塔座Z移动到Y。如图3.13所示。
图3.12 将编号为1的圆盘从塔座X移动到Z
图3.13 将编号为2的圆盘从塔座X移动到Y，编号为1的圆盘从塔座Z移动到Y
第2个过程完成编号为3的圆盘从塔座X移动到Z。如图3.14所示。
第3个过程通过调用Hanoi（2,y,x,z）实现圆盘移动。通过再次递归完成将编号为1的圆盘从塔座Y移动到X，如图3.15所示。将编号为2的圆盘从塔座Y移动到Z，将编号为1的圆盘从塔座X移动到Z。如图3.16所示。
图3.14 将编号为3的圆盘从塔座X移动到Z
图3.15 将编号为1的圆盘从塔座Y移动到X
图3.16 将编号为2的圆盘从塔座Y移动到Z，编号为1的圆盘从塔座X移动到Z
在递归调用过程中，运行被调用函数前系统要完成3件事情：
（1）将所有参数和返回地址传递给被调用函数保存。
（2）为被调用函数的局部变量分配存储空间。
（3）将控制转移到被调用函数的入口。
当被调用函数执行完毕，返回到调用函数之前，系统同样需要完成3个任务：
（1）保存被调用函数的执行结果。
（2）释放被调用函数的数据存储区。
（3）将控制转到调用函数的返回地址处。
在多层嵌套调用时，递归调用过程的原则是后调用的先返回，因此，递归调用是通过栈实现的。函数递归调用过程中，在递归结束前，每调用一次，就进入下一层。当一层递归调用结束时，返回到上一层。
为了保证递归调用的正确执行，系统设置了一个工作栈作为递归函数运行期间使用的数据存储区。每一层递归包括实在参数、局部变量及上一层的返回地址等构成一个工作记录。每进入下一层，就产生一个新的工作栈记录被压入栈顶。每返回到上一层，就从栈顶弹出一个工作记录。因此，当前层的工作记录是栈顶工作记录，被称为活动记录。递归过程产生的栈由系统自动管理，类似用户使用的栈。递归的实现本质上就是把嵌套调用变成栈实现。