递归算法是设计一个方法（函数），并在方法（函数）中不断调用自身。其结构如下：

也可以是间接的调用自己，如：

使用递归算法，是把较复杂的问题（规模为n）的求解，分解为比原问题更为简单的问题（规模小于n），直到规模为1为止以得到最终的解。例如，n！可以分解为（n-1）！，（n-1）！又可以分解为（n-2）！，……直至1！=1为止。

使用递归算法解决问题有以下特点：

1）递归就是在方法（函数）当中调用自身。

2）在使用递归时，方法（函数）中必须有一个明确的递归结束条件，也就是递归出口。

3）递归算法解题通常显得很简洁，但递归算法解题的运行效率较低，所以一般不提倡用递归算法设计程序。通常递归算法可以使用递推算法来完成。

4）在进行递归调用时，系统使用栈存储为每一次调用分别设置的返回点和局部变量，当递归层数过多时容易造成栈的溢出，引起程序崩溃。

使用递归算法进行程序设计时，要注意以下几个方面：

1）每次调用在规模上都应该有所减小，最后趋向于递归出口。

2）相邻两次调用之间要有紧密的关联，前一次要为后一次做准备。通常前一次的输出就作为后一次的输入。

3）在问题的规模到达最小时，应该直接给出解答而不能再进行递归调用。因此递归调用都应该在一定的条件下进行，无条件递归调用将会使程序无限循环而不能正常结束，也会因为栈的溢出而使得程序崩溃。

【例9-10】使用递归算法，计算1～100的累加和。

程序思路：整数n的累加和f（n）=n+f（n-1），形成递归关系。而f（1）=1，为递归出口。

程序运行结果：

5050

【例9-11】使用递归算法，求Faibonacci序列数。

程序思路：Faibonacci序列有fib（n）=fib（n-1）+fib（n-2），形成递归关系。且有fib（0）=0，fib（1）=1，构成递归出口。

程序运行结果：

1 1 2 3 5 8 13 21 34 55 89 144

【例9-12】汉诺塔问题：这是一个经典的递归算法问题。创世纪时Benares有一座波罗教塔，由三支钻石棒所支撑，神在第一根棒上放置64个由上至下依由小至大排列的金盘，命令僧侣们将所有的金盘从第一根石棒移至第三根石棒，移动时可以借助第二根棒，但要求必须是大盘在小盘之下。设计金盘的移动算法。

程序思路：假设A棒上有n个盘子，最下面的大盘编号为n，最上面的小盘编号为1。我们将这n个盘子分解为第n个盘和其他n-1个盘子两部分（相当于只有两个盘子）。这时，将n盘和其他n-1个盘的移动（A→C）调用方法move（n′，A′′，B′′，C′）完成。在这个方法中，移动过程分解为以下3个步骤。

1）先将A上的n-1个盘子移动到B，调用方法move（n-1，a，c，b）。(www.daowen.com)

2）将A座上的第n个盘子移动到C座上。这个盘子已经到位，不能再动，这时只显示第n个盘的移动结果A→C。

3）再将B上的n-1个盘子，又分解为第n-1个盘和其他n-2个盘两个部分，借助A棒，将第n-1个盘移到C上：move（n-1，b，a，c）。

以上3个步骤反复进行，直到最小的盘子（第1个盘）移动到C座。这样就完成了递归过程。

程序运行结果：

盘子个数：3

盘1：A→C

盘2：A→B

盘1：C→B

盘3：A→C

盘1：B→A

盘2：B→C

盘1：A→C

递归算法执行时分成递进和回归两个阶段。递进阶段把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。如求Faibonacci序列数，求解fib（n）时，把它递进到求解fib（n-1）和fib（n-2）。也就是说，为计算fib（n），必须先计算fib（n-1）和fib（n-2），而计算fib（n-1）和fib（n-2），又必须先计算fib（n-3）和fib（n-4）。依次类推，直至计算出fib（1）和fib（0），得到递归出口的结果1和0。所以在递进阶段，必须要有递归出口来终止递进的过程。

在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib（1）和fib（0）后，返回得到fib（2）的结果，……，在得到了fib（n-1）和fib（n-2）的结果后，返回得到fib（n）的结果。

使用递归算法时要注意，方法中的局部变量和参数的作用域仅局限于当前调用层，当递推进入下一层时，原来层次上的参数和局部变量便推入栈中被保存起来。也就是说，方法在递归调用时，每一次调用有当前层的参数和局部变量，这些变量以及调用返回的地址通过栈存储的方式进行保存。当递归层数过多时，所有变量及返回地址的累积很容易造成栈的溢出。

下面介绍递推与递归的比较。

与递归算法相比，递推算法免除了数据进出栈的过程，也就是说，不需要对问题进行分解，而向最小规模靠拢，只要直接从边界出发，直到求出最终的解。

比如阶乘计算，使用递归f（n）=n*f（n-1），如f（3）的运算，其递归的数据流动过程如下：

f（3）→f（2）→f（1）→f（0）=1→f（1）=1*1→f（2）=2*1→f（3）=3*2

而递推只要如下过程：

f（0）=1→f（1）=1*1→f（2）=2*1→f（3）=3*2

由此可见，递推的效率要高一些，在可能的情况下应尽量使用递推。但是递归作为比较基础的算法，使用时有很大的灵活性，可以使得程序变得灵活简单。它的作用也是不能忽视的。