2.3 递归算法思想
知识点讲解：光盘：视频讲解\第2章\递归算法思想.avi
因为递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可。在本节的内容中，将详细讲解递归算法思想的基本知识。
2.3.1 递归算法基础
在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3个特点。
① 递归过程一般通过函数或子过程来实现。
② 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。
③ 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。
在使用递归算法时，读者应该注意如下4点。
① 递归是在过程或函数中调用自身的过程。
② 在使用递归策略时，必须有一个明确的递归结束条件，这称为递归出口。
③ 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。
④ 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。
2.3.2 实践演练——解决“汉诺塔”问题
为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解递归算法思想在编程中的基本应用。
实例2-5 使用递归算法解决“汉诺塔”问题
源码路径 光盘\daima\2\hannuo.c
问题描述：寺院里有3根柱子，第一根有64个盘子，从上往下盘子越来越大。方丈要求小和尚A1把这64个盘子全部移动到第3根柱子上。在移动的时候，始终只能小盘子压着大盘子，而且每次只能移动一个。
方丈发布命令后，小和尚A1就马上开始了工作，下面看他的工作过程。
（1）聪明的小和尚A1在移动时，觉得很难，另外他也非常懒惰，所以找来A2来帮他。他觉得要是A2能把前63个盘子先移动到第二根柱子上，自己再把最后一个盘子直接移动到第三根柱子，再让A2把刚才的前63个盘子从第二根柱子上移动到第三根柱子上，整个任务就完成了。所以他找了另一个小和尚A2，然后下了如下命令：
① 把前63个盘子移动到第二根柱子上；
② 把第64个盘子移动到第三根柱子上后；
③ 把前63个盘子移动到第三根柱子上；
（2）小和尚A2接到任务后也觉得很难，所以他也和A1想的一样：要是有一个人能把前62个盘子先移动到第三根柱子上，再把最后一个盘子直接移动到第二根柱子，再让那个人把刚才的前62个盘子从第三根柱子上移动到第三根柱子上，任务就算完成了。所以他也找了另外一个小和尚A3，然后下了如下命令：
① 把前62个盘子移动到第三根柱子上；
② 自己把第63个盘子移动到第二根柱子上后；
③ 把前62个盘子移动到第二根柱子上；
（3）小和尚A3接了任务，又把移动前61个盘子的任务“依葫芦画瓢”的交给了小和尚A4，这样一直递推下去，直到把任务交给了第64个小和尚A64为止。
（4）此时此刻，任务马上就要完成了，唯一的工作就是A63和A64的工作了。
小和尚A64移动第1个盘子，把它移开，然后小和尚A63移动给他分配的第2个盘子。
小和尚A64再把第1个盘子移动到第2个盘子上。到这里A64的任务完成，A63完成了A62交给他的任务的第一步。
算法分析：从上面小和尚的工作过程可以看出，只有A64的任务完成后，A63的任务才能完成，只有小和尚A2～小和尚A64的任务完成后，小和尚A1剩余的任务才能完成。只有小和尚A1剩余的任务完成，才能完成方丈吩咐给他的任务。由此可见，整个过程是一个典型的递归问题。接下来我们以有3个盘子来分析。
第1个小和尚命令：
① 第2个小和尚先把第一根柱子前2个盘子移动到第二根柱子，借助第三根柱子；
② 第1个小和尚自己把第一根柱子最后的盘子移动到第三根柱子；
③ 第2个小和尚你把前2个盘子从第二根柱子移动到第三根柱子。
非常显然，第②步很容易实现。
其中第一步，第2个小和尚有2个盘子，他就命令：
① 第3个小和尚把第一根柱子第1个盘子移动到第三根柱子（借助第二柱子）；
② 第2个小和尚自己把第一根柱子第2个盘子移动到第二根柱子上；
③ 第3个小和尚把第1个盘子从第三根柱子移动到第二根柱子。
同样，第②步很容易实现，但第3个小和尚只需要移动1个盘子，所以他也不用再下派任务了（注意：这就是停止递归的条件，也叫边界值）。
第③步可以分解为，第2个小和尚还是有2个盘子，于是命令：
① 第3个小和尚把第二根柱子上的第1个盘子移动到第一根柱子；
② 第2个小和尚把第2个盘子从第二根柱子移动到第三根柱子；
③ 第3个小和尚你把第一根柱子上的盘子移动到第三根柱子。
分析组合起来就是：1→3,1→2,3→2，借助第三根柱子移动到第二根柱子；1→3是自私人留给自己的活；2→1,2→3,1→3是借助别人帮忙，第一根柱子移动到第三根柱子一共需要七步来完成。
如果是4个盘子，则第一个小和尚的命令中第①步和第③步各有3个盘子，所以各需要7步，共14步，再加上第1个小和尚的第①步，所以4个盘子总共需要移动7+1+7=15步；同样，5个盘子需要15+1+15=31步，6个盘子需要31+1+31=63步……由此可以知道，移动n个盘子需要（2n-1）步。
假设用hannuo（n, a, b, c）表示把第一根柱子上的n个盘子借助第2根柱子移动到第3根柱子。由此可以得出如下结论。
第①步的操作是hannuo(n-1,1,3,2)，第③步的操作是hannuo(n-1,2,1,3)。
具体实现：根据上述算法分析，编写实现文件hannuo.c，具体代码如下所示。
move(int n, int x, int y, int z)//移动函数，根据递归算法编写
{
if (n==1)
printf("%c-->%c\n", x, z);
else
{
move(n-1, x, z, y);
printf("%c-->%c\n", x, z);
{
getchar(); }
move(n-1, y, x, z);
}
}
main()
{
int h;
printf("输入盘子个数： "); //提示输入盘子个数
scanf("%d", &h);
printf("移动%2d个盘子的步骤如下：\n", h);
move(h, 'a', 'b', 'c'); //调用前面定义的函数开始移动，依次输出一定步骤
system("pause");
}
执行后先输入移动盘子的个数，按下【Enter】键后将会显示具体步骤。执行效果如图2-6所示。
图2-6 “汉诺塔”问题执行效果
2.3.3 实践演练——解决“阶乘”问题
为了说明递归算法的基本用法，接下来将通过一个具体实例的实现过程，详细讲解使用递归算法思想解决阶乘问题的方法。
实例2-6 使用递归算法解决“阶乘”问题
源码路径 光盘\daima\2\yunsuan.c
问题描述：阶乘（factorial）是基斯顿·卡曼（Christian Kramp）于1808年发明的一种运算符号。自然数由1～n的n个数连乘积叫作n的阶乘，记作n!。
例如所要求的数是4，则阶乘式是1×2×3×4，得到的积是24，即24就是4的阶乘。
例如所要求的数是6，则阶乘式是1×2×3×…×6，得到的积是720，即720就是6的阶乘。
例如所要求的数是n，则阶乘式是1×2×3×…×n，设得到的积是x, x就是n的阶乘。
在下面列出了0～10的阶乘。
0! =1
1! =1
2! =2
3! =6
4! =24
5! =120
6! =720
7! =5040
8! =40320
9! =362880
10! =3628800
算法分析：假如计算6的阶乘，则计算过程如图2-7所示。
图2-7 计算6的阶乘的过程
具体实现：根据上述算法分析，使用递归法编写文件jiecheng.c，具体代码如下所示。
#include <stdio.h>
int fact(int n);
int main()
{
int i;
printf("输入要计算阶乘的一个整数：");
scanf("%d", &i);
printf("%d的阶乘结果为：%d\n", i, fact(i));
getch();
return 0;
}
int fact(int n)
{
if(n<=1)
return 1;
else
return n*fact(n-1);
}
执行后如果输入“6”并按下【Enter】键，则会输出6的阶乘是720，执行效果如图2-8所示。
图2-8 计算6的阶乘的执行效果