3.3 栈与递归的实现
3.3 栈与递归的实现
栈还有一个重要的应用就是在程序设计语言中实现递归。一个函数直接调用自己或通过一系列的调用语句间接地调用自己，就称做递归调用。
递归是程序设计中一个强有力的工具。其一，有很多数学函数是递归定义的，如大家熟悉的阶乘函数：
|
Fact(n)= |
=0
n·Fact(n-1) 若
>0
其二，有的数据结构，如二叉树、广义表等，由于结构本身固有的递归特性，因而它们的操作可递归地描述；其三，还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，如八皇后问题、汉诺塔问题等。
【例3-4】19世纪在欧洲有一个游戏称为汉诺塔（Towers of Hanoi），有64个大小不同的金盘子，3个镶钻石的柱子分别为A、B、C，现想将64个金盘子从A柱子移至C柱子，但可以借助B柱子，游戏规则如下所述：
（1）每次只能移动一个盘子。
（2）盘子有大小之分，而且大盘子在下，小盘子在上。
假设有n个金盘子（1，2，3，…，n-1），数字越大表示重量越重，其搬移的算法如下：
假使n=1则搬移第1个盘子从A至C；否则搬移n-1个盘子从A至B。搬移第n个盘子从A至C。搬移n-1个盘子从B至C。
用C语言编写的程序如下所示：
void tower(char from,char to,char aux,int n)
{
if(n==1)
printf("Move disk 1 from %c to %c\n",from,to);
else
{
tower(from,aux,to,n-1); /* 递归调用 */
printf("Move disk %d from %c to %c\n",n,from,to);
tower(aux,to,from,n-1); /* 递归调用 */
}
}
以3个金盘子为例：从A柱子移到C柱子，而B为辅助的柱子，如图3-4所示。
图3-4 含有3个金盘子的汉诺塔
说明：
（1）将1号金盘子从A移到C。
（2）将2号金盘子从A移到B，结果如图3-5所示。
（3）将1号金盘子由C移到B。
（4）将3号金盘子由A移到C，结果如图3-6所示。
（5）将1号金盘子由B移到A。
（6）将2号金盘子由B移到C，结果如图3-7所示。
（7）将1号金盘子由A移到C，结果如图3-8所示。
图3-5 执行完第（1）、（2）步后含有3个金盘子的汉诺塔
图3-6 执行完第（3）、（4）步后含有3个金盘子的汉诺塔
图3-7 执行完第（5）、（6）步后含有3个金盘子的汉诺塔
图3-8 执行完第（7）步后含有3个金盘子的汉诺塔
至此操作完成。
程序的跟踪图如图3-9所示。
利用函数递归求汉诺塔问题的实现程序如下。
#include <stdio.h>
#include <conio.h>
/* 函数原型声明*/
void HanoiTower(int,char,char,char);
void main()
{
int n;
char A='A',B='B',C='C';
printf("-----Hanoi Tower Implementaion----\n");
/*输入共有几个盘子在A柱子上*/
printf("How many disks in A ? ");
scanf("%d",&n);
图3-9 实现含有3个金盘子的汉诺塔的程序跟踪图
if(n==0)
printf("no disk to move\n");
else
HanoiTower(n,A,B,C);
}
/* 递归函数调用求汉诺塔之解*/
void HanoiTower(int n,char a,char b,char c)
{
if(n==1)
printf("Move disk 1 from %c -> %c\n",a,c);
else
{
/*将A上n-1个盘子借助C移至B */
HanoiTower(n-1,a,c,b);
printf("Move disk %d from %c -> %c\n",n,a,c);
/*将B上n-1个盘子借助A移至C */
HanoiTower(n-1,b,a,c);
}
}
-----Hanoi Tower Implementaion
How many disks in A?3
Move disk 1 from A->C
Move disk 2 from A->B
Move disk 1 from C->B
Move disk 3 from A->C
Move disk 1 from B->A
Move disk 2 from B->C
Move disk 1 from A->C
Press any key to continue
汉诺塔问题的目的是在3根柱子中，将n个盘子从A柱子移到C柱子上，每次只移动一个盘子，而且必须遵守每个盘子都比其上面的盘子还要大的原则。
汉诺塔问题的想法必须针对最底端的盘子。必须先把A柱子顶端n-1个盘子想办法（借助C柱子）移至B柱子，然后才能将最底端的盘子移至C柱子。此时C柱子有最大的盘子，B柱子总共有n-1个盘子，A柱子则无。只要再借助A柱子，将B柱子n-1个盘子移往C柱子即可：
HanoiTower(n-1,A,C,B);
将A柱子顶端n-1个盘子借助C柱子移至B柱子。
HanoiTower(n-1,B,A,C);
将B柱子上的n-1个盘子借助A柱子移至C柱子。