靳润昭C语言教程讲义 2001年2月17日 也为1,将使递归终止。然后可逐层退回。 下面我们再举例说明该过程。设执行本程序时输入为5,即求5!。在主函数中的调用 语句即为y=f(5),进入函数后,由于n=5,不等于0或1,故应执行f=(n-1)n即f(51)*5 该语句对f作递归调用即f(4)。 进行四次递归调用后,ff函数形参取得的值变为1,故不再继续递归调用而开始逐层返 回主调函数。ff(1)的函数返回值为1,ff(2)的返回值为1*2=2,ff(3)的返回值为2*3=6, ff(4)的返回值为6*4=24,最后返回值ff(5为24*5=120。 例8.5也可以不用递归的方法来完成。如可以用递推法,即从1开始乘以2,再乘以3 直到n。递推法比递归法更容易理解和实现。但是有些问题则只能用递归算法才能实现。典 型的问题是 Hanoi塔问题。 【例8.6】 Hanoi塔问题 块板上有三根针,A,B,C。A针上套有64个大小不等的圆盘,大的在下,小的在上 如图5.4所示。要把这64个圆盘从A针移动C针上,每次只能移动一个圆盘,移动可以借 助B针进行。但在任何时候,任何针上的圆盘都必须保持大盘在下,小盘在上。求移动的步 骤 本题算法分析如下,设A上有n个盘子。 如果n=1,则将圆盘从A直接移动到C。 如果n=2,则: 1.将A上的n-1(等于1)个圆盘移到B上 2.再将A上的一个圆盘移到C上 3.最后将B上的n-1(等于1)个圆盘移到C上。 如果n=3,则 A.将A上的n-1(等于2,令其为m)个圆盘移到B(借助于C),步骤如下: (1)将A上的n-1(等于1)个圆盘移到C上 (2)将A上的一个圆盘移到B。 (3)将C上的n-1(等于1)个圆盘移到B B.将A上的一个圆盘移到C C.将B上的n-1(等于2,令其为n)个圆盘移到C(借助A),步骤如下 (1)将B上的n-1(等于1)个圆盘移到A (2)将B上的一个盘子移到C (3)将A上的n-1(等于1)个圆盘移到C。 到此,完成了三个圆盘的移动过程。 从上面分析可以看出,当n大于等于2时,移动的过程可分解为三个步骤 第一步把A上的n-1个圆盘移到B上 第二步把A上的一个圆盘移到C上 第三步把B上的n-1个圆盘移到C上:其中第一步和第三步是类同的 当n=3时,第一步和第三步又分解为类同的三步,即把n-1个圆盘从一个针移到另 个针上,这里的n=n-1。显然这是一个递归过程,据此算法可编程如下: move(int n, int x, int y, int z) if(n==1) printf(%c->%c\n",x, z) 1 第11页靳润昭 C 语言教程讲义 2001 年 2 月 17 日 第11页 也为 1，将使递归终止。然后可逐层退回。 下面我们再举例说明该过程。设执行本程序时输入为 5，即求 5!。在主函数中的调用 语句即为 y=ff(5)，进入 ff 函数后，由于 n=5,不等于 0 或 1，故应执行 f=ff(n-1)*n,即 f=ff(5-1)*5。 该语句对 ff 作递归调用即 ff(4)。 进行四次递归调用后，ff 函数形参取得的值变为 1，故不再继续递归调用而开始逐层返 回主调函数。ff(1)的函数返回值为 1，ff(2)的返回值为 1*2=2，ff(3)的返回值为 2*3=6， ff(4)的返回值为 6*4=24，最后返回值 ff(5)为 24*5=120。 例 8.5 也可以不用递归的方法来完成。如可以用递推法，即从 1 开始乘以 2，再乘以 3… 直到 n。递推法比递归法更容易理解和实现。但是有些问题则只能用递归算法才能实现。典 型的问题是 Hanoi 塔问题。 【例 8.6】Hanoi 塔问题 一块板上有三根针，A，B，C。A 针上套有 64 个大小不等的圆盘，大的在下，小的在上。 如图 5.4 所示。要把这 64 个圆盘从 A 针移动 C 针上，每次只能移动一个圆盘，移动可以借 助 B 针进行。但在任何时候，任何针上的圆盘都必须保持大盘在下，小盘在上。求移动的步 骤。 本题算法分析如下，设 A 上有 n 个盘子。 如果 n=1，则将圆盘从 A 直接移动到 C。 如果 n=2，则： 1.将 A 上的 n-1(等于 1)个圆盘移到 B 上； 2.再将 A 上的一个圆盘移到 C 上； 3.最后将 B 上的 n-1(等于 1)个圆盘移到 C 上。 如果 n=3，则： A. 将 A 上的 n-1(等于 2，令其为 n`)个圆盘移到 B(借助于 C)，步骤如下： (1)将 A 上的 n`-1(等于 1)个圆盘移到 C 上。 (2)将 A 上的一个圆盘移到 B。 (3)将 C 上的 n`-1(等于 1)个圆盘移到 B。 B. 将 A 上的一个圆盘移到 C。 C. 将 B 上的 n-1(等于 2，令其为 n`)个圆盘移到 C(借助 A)，步骤如下： (1)将 B 上的 n`-1(等于 1)个圆盘移到 A。 (2)将 B 上的一个盘子移到 C。 (3)将 A 上的 n`-1(等于 1)个圆盘移到 C。 到此，完成了三个圆盘的移动过程。 从上面分析可以看出，当 n 大于等于 2 时，移动的过程可分解为三个步骤： 第一步 把 A 上的 n-1 个圆盘移到 B 上； 第二步 把 A 上的一个圆盘移到 C 上； 第三步 把 B 上的 n-1 个圆盘移到 C 上；其中第一步和第三步是类同的。 当 n=3 时，第一步和第三步又分解为类同的三步，即把 n`-1 个圆盘从一个针移到另一 个针上，这里的 n`=n-1。 显然这是一个递归过程，据此算法可编程如下： move(int n,int x,int y,int z) { if(n==1) printf("%c-->%c\n",x,z); else