高级语言讲课第24次课c2

1、第十章 递归程序设计计算n！递归程序设计程序设计实例计算算术表达式的值间接递归递归程序执行过程作业: 10.3练习: 10.2 10.410.1 计算n!递归程序设计例10-1 编一个函数 factorial 计算阶乘 !按过去程序设计思想，该函数应该写成： int factorial ( int n ) int i,p; p=1; for ( i=1 ; i0按照该定义，! 就是一个简单的条件语句和表达式计算，可以编出如下函数： int factorial ( int n ) if ( n=0 ) return 1; else return n*factorial(n-1); 问题：在函数

2、factorial 内又调用函数 factorial 本身，行吗？回答：行！ 按作用域规则，在函数 factorial 内又调用函数 factorial 本身是合法的；其次 C 系统保证上述调用过程执行的正确性，这就是递归。从静态行文看，在定义一个函数时，若在定义它的内部，又出现对它本身的调用，则称该函数是递归的，或递归定义的。从动态执行角度看，当调用一个函数时，在进入相应函数，还没退出（返回）之前，又再一次的调用它本身，而再一次进入相应函数，则称之为递归，或称之为对相应函数的递归调用。 称递归定义的函数为递归函数。上述函数 factorial 就是递归函数。若计算 5! ，使用函数调用fac

3、torial(5) ，观察其计算过程: return 5*f(4) return 120f(4)f(3)f(2)f(1)f(0)return 4*f(3)return 3*f(2)return 2*f(1)return 1*f(0)return 1return 24return 1return 1int factorial ( int n ) if ( n=0 ) return 1; else return n*factorial(n-1); void main() printf(“%dn”,factorial (5) );return 2return 6【例10.2】 X 的 n 次幂，可以

4、定义为float power ( float x, int n ) if ( n=0 )return 1 ;else return x * power(x,n-1) ;【例10.3】 n 次勒让德多项式计算它的递归函数是: float p ( int n , float x ) if ( n=0 ) return 1 ; else if (n=1) return x ; else return ( (2*n-1)*x*p(n-1,x) - (n-1)*p(n-2,x) )/n ; 递归程序设计的思想体现在：用逐步求精原则，先把一个问题分解成若干子问题这些子问题中有问题的与原始问题具有相同的特征

5、属性，至多不过是某些参数不同，规模比原来小了此时，就可以对这些子问题实施与原始问题同样的分析算法，直到规模小到问题容易解决或已经解决时为止。也就是说，若将整个问题的算法设计成一个函数，则解决这个子问题的算法就表现为对相应函数的递归调用.编写递归程序要注意：递归程序漂亮、好看、好读、风格优美，但执行效率低。计算! 的函数即可以写成循环形式，也可以写成递归形式。但是有些循环程序写成递归很困难。反之，有些递归程序写成循环也很困难，甚至是不可能的。终结条件。程序一定要能终止，不能无限递归下去。使用全局量要特别小心。用不好，单元发生冲突，将导致程序出错。 例10-4汉诺（ Hanoi ）塔游戏该问题又称

6、世界末日问题。相传，古印度布拉玛婆罗门神庙的憎侣们，当时作一种被称为 Hanoi塔的游戏。该游戏是：在一个平板上，有三根钻石针；在其中一根针上有成塔型落放的大小不等的64片金片；要求把这64片金片全部移到另一根钻石针上。移动规则是：每次只允许移动一片金片；移动过程中的任何时刻，都不允许有较大的金片放在较小的金片的上面；移动过程中，三根钻石针都可以利用，但是金片不许放在除钻石针以外的任何地方。不论白天黑夜都有一个憎侣在移动。据说当64片金片全部从一根钻石针移到另一根钻石针上那天，就是世界的末日。到那时他们的虔诚信徒可以升天，而其他人则要下地狱。当然这只是传说，按照规则把 64 片金片全部从一根针

7、移到另一根针上，总的移动次数是 264-1次，若一秒移动一次，不发生错误，日夜不停的移动，约需 5849 亿年。而太阳系的寿命仅有100150亿年而已。请编程序，打印金片的移动顺序。10.2 程序设计实例解：不妨设三根钻石针顺次编号为 a 、b 、c ；开始所有 64 片金片全部在 a 针上；现在要把它们移动到 b 针上；移动过程中 c 针可以利用。如图所示 . .64片 a b c63片 . .63片 . .64片试想，若能够把a 针上的64片金片全部移动到b针上，必须能够先把a针顶部的63片金片移到c针上。现在，可以很容易的把a针上的一片金片移到 b 针上。最后，再按照把a针上的63片金片

8、移到c针上的算法，把c针上的63片金片全部移到b针上。从而，完成了题目要求的工作。重新观察上述过程： 怎样进行移动？开始就遇到把a针最上边的金片先移到b针上，还是先移到c针上？没有任何根据作出决定，按一般方法是不好解决这个问题的。下边换一个角度来考虑该问题：按这个想法，移动 64 片金片的问题可以被分解成：把a针上63片金片，从a针移到c针上，移动过程中b针可用；把a针上一片金片移到b针上；把c针上63片金片，从c针移到b针上，移动过程中a针可用。到此，问题虽然没有解决，但是已经向解的方向前进了一步，移动64 片金片的问题变成移动 63 片金片的问题了。这一步虽然很小, 甚至是微不足道的，但是

9、却是十分重要的。 . .64片 a b c63片 . .63片 . .64片设若有一函数 move( n , x , y , z )能够完成：“把 x 针上的 n 片金片，移动到 y 针上，移动过程中可以利用 z 针。”，则上述原始问题可以描述成对 move 的调用：move( 64 , a , b , c )移动过程也可以描述成对 move 的调用：move( 63 , a , c , b ) move( 63 , c , b , a )考虑move函数: 按分解移动 64 片金片问题的思路，问题：“把 x 针上的 n 片金片，移动到 y 针上，移动过程中 z 针可用”可以被分解成：把 x

10、针上 n-1 片金片，从 x 针移到 z 针，移动过程中 y 针可用把 x 针上一片金片移到 y 针上；把 z 针上 n-1 片金片，从 z 针移到 y 针，移动过程中 x 针可用 按该分解算法，并考虑递归出口 (显然，当移动金片的片数为 0 时，便不用移动了)，写出move函数。 以64、a、b、c为实在参数调用该move函数，便可以解决Hanoi 塔问题。 最后得到完整的 Hanoi 塔解法程序如下void moveone ( char u , char v ) printf ( “%c - %cn” , u , v );void move ( int n, char x, char y,

11、 char z ) if ( n0 ) move( n-1 , x,z,y );moveone( x,y );move( n-1 , z,y,x ) int main(void) int n ;printf( “pleace input n:”); scanf( “%d” , &n ); move ( n , a , b , c ) 执行 hanoi 程序时不要输入太大的 n ，我们执行该程序。执行主程序：1、输出提示信息；2、要求输入金片个数 n ，设输入“3”；3、调用move函数：进入move ；n=30， 参数替换后，实际printf( “pleace input n:”);scanf

12、( “%d” , &n );move ( n , a , b , c )move( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a )执行调用move ( 2 , a , c , b )：调用move函数：进入move ；n=20，执行参数替换后，实际是执行：printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( n-1

13、 , x , z , y );moveone( x , y );move( n-1 , z , y , x );move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a );move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a );执行调用move ( 1 , a , b , c )：调用move函数：进入move ；n=10，执行参数替换后，实际是执行：printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a

14、, b , c )move( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a );move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a );move( 0 , a , c , b );moveone( a , b );move( 0 , c , b , a );执行move( 0 , a , c , b )：调用move函数，进入move ；n=0

15、，返回。调用moveone ，打印“a-b”调用move函数，进入move ；n=0，返回。move函数执行结束，返回。printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a )move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a )move( 0 , a , c , b );moveone( a , b );move( 0 , c ,

16、 b , a );a-b 调用moveone ，打印“a-c”调用move函数，进入move ；n=10，执行参数替换后，实际执行printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a );move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a );a-ba-c move( n-1 , x , z , y );moveone( x , y

17、 );move( n-1 , z , y , x );move( 0 , b , a , c );moveone( b , c );move( 0 , a , c , b );调用move函数，进入move ；n=0，返回。调用moveone ，打印“b-c”调用move函数，进入move ；n=0，返回。move函数执行结束，返回。move函数执行结束，返回。调用moveone ，打印“a-b”执行move( 2 , c , b , a )printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 ,

18、 a , c , b );moveone( a , b );move( 2 , c , b , a );move( 1 , a , b , c );moveone( a , c );move( 1 , b , c , a );a-ba-cb-ca-bmove( 0 , b , a , c );moveone( b , c );move( 0 , a , c , b );调用move ( 2 , c , b , a )，进入move 实际执行调用move ( 1 , c , a , b )，进入move 实际执行调用move函数，进入move ；n=0，返回。调用moveone ，打印“c-a”

19、调用move函数，进入move ；n=0，返回。 move函数执行结束，返回。printf( “pleace input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a )a-ba-ca-ca-bc-amove( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 1 , c , a , b );moveone( c , b );move( 1 , a , b

20、 , c )move( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 0 , c , b , a );moveone( c , a );move( 0 , b , a , c )调用moveone ，打印“c-b”调用move ( 1, a , b , c )，进入move ；实际执行调用move函数，进入move ；n=0，返回。调用moveone ，打印“a-b”调用move函数，进入move ；n=0，返回。move函数执行结束，返回。move函数执行结束，返回。程序执行结束。printf( “pleace

21、 input n:”);scanf( “%d” , &n );move ( n , a , b , c )move( 2 , a , c , b );moveone( a , b );move( 2 , c , b , a )a-ba-cb-ca-bc-ac-ba-bmove( 1 , c , a , b );moveone( c , b );move( 1 , a , b , c )move( n-1 , x , z , y );moveone( x , y );move( n-1 , z , y , x )move( 0 , a , c , b );moveone( a , b );mov

22、e( 0 , c , b , a )按程序输出的移动顺序，实际移动。a-ba-cb-ca-bc-ac-ba-b a b c例10.5 三个齿轮啮合问题 设有三个齿轮互相衔接，求当三个齿轮的某两对齿互相衔接后到下一次这两对齿再互相衔接，每个齿轮最少各转多少圈。 解:首先把问题数学化，这是求最小公倍数的问题。每个齿轮需转圈数是三个齿轮齿数的最小公倍数除以自己的齿数。设 三个齿轮的齿数分别为:na、nb、nc ； 啮合最小圈数分别为:ma、mb、mc ； 三齿轮齿数的最小公倍数为k3 。计算步骤表示为：开始读入三齿轮齿数求三齿数的最小公倍数 k3分别计算啮合的最小圈数输出结果结束 读入三齿轮齿数和输

23、出结果，分别只是一次调用读或写函数，不必求精。 求精计算三齿数的最小公倍数k3 。可以把该问题分解成 先求两个齿数na与nb的最小公倍数 k2 ， 然后再求k2与第三个齿数 nc 的最小公倍数 k3 ， k3 即为na、nb、nc三个齿轮齿数的最小公倍数。设已经有求两个数的最小公倍数的函数 int lowestcm( int x, int y )则该求精过程可表示成 。求三齿数的最小公倍数 k3=lowestcm( lowestcm(na,nb), nc )结束求精求两个数的最小公倍数的函lowestcm 。 x、y 的最小公倍数是 x、y 的积除以 x、y 的最大公约数。设已经有求两个数的最

24、大公约数的函数 int gcd(int x, int y)则该求精过程可表示成： int lowestcm(int x , int y)return x*y / gcd(x,y)结束def欧几里德辗转相除法u % v R1v % R1 R2R1% R2 R3R2 % R3 R4 Rn-2 % Rn-1 Rn=0 Rn-1 为正整数u 、v的最大公因数 继续求精两个数的求最大公约数：已经知道“展转相除法”求u、v最大公约数的计算过程如下 上述“展转相除法”求两个数的最大公约数的函数int gcd(int x, int y)可以定义为 被求精成下图int gcd( int x, int y)结束y

25、0return gcd(y , x % y)return x最后，分别计算啮合的最小圈数可以被求精成下图 。开始ma = k3 / namb = k3 / nbmc = k3 / nc结束/* PROGRAM mesh */#include “stdio.h” /* 函数原型部分 *int lowestcm3(int x, int y，int z) ；/ 计算三个数的最小公倍数 int lowestcm2(int x, int y) ； / 计算两个数最小公倍数int gcd(int x, int y) ; / 计算x,y的最大公约数/* 主程序开始 */void main( ) int na

26、,nb,nc,k3; printf(please input n1 n2 n3:); scanf(“%d%d%d”,&na,&nb,&nc); k3 = lowestcm3(na,nb,nc); printf (“FOR mesh the first mnst rotate about %4d rings.n” , k3 / na ); printf (“FOR mesh the second mnst rotate about %4d rings.n” , k3 / nb ); printf (“FOR mesh the third mnst rotate about %4d rings.n

27、” , k3 / nc );/* 计算三个数的最小公倍数 */int lowestcm3(int x, int y，int z) return lowestcm2(lowestcm2(x,y),z);/* 计算两个数的最小公倍数 */int lowestcm2(int x, int y) return x*y / gcd(x,y); /* lowestcm */* 计算x,y的最大公约数 */int gcd(int x, int y) if (y=0) return x; else return gcd( y , x % y ); /* gcd */在本例中，函数gcd自己调用自己，产生直接递

28、归函数lowestcm3的语句return lowestcm2( lowestcm2 (x,y) , z );调用函数lowestcm2的执行过程是：1.调用开始，在进入函数lowestcm2；2.计算实在参数，又再一次调用函数lowestcm2； 递归的动态含义是：在调用函数，进入一个函数后还没退出之前，又再一次调用该函数而进入该函数,同样产生递归，这种递归称为“由调用引起的递归”。函数 lowestcm2 本身定义看不出递归，但是他调用的函数gcd存在递归。 【例10.6】从前 n 个自然数 1 , 2 , 3 , . , n 中取 r 个数作组合，打印全部所有组合。 例如，n=5 、r=

29、3 ，有如下的10种组合。 1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5解本题的一般想法是使用 r 重循环 for ( i1 = 1 ; i1 =n-r+1 ; i1 + ) for ( i2 = i1+1 ; i2 = n-r+2 ; i2 + ) . . for ( ir = ir-1+1 ; ir = n ; ir + ) 印( i1 , . , ir )但是，由于 r 是可变的，所以循环嵌套层数亦是可变的，因此不知道应该用多少个 i 。换一个角度想问题。从前 n 个自然数 1 , 2 , 3 , . , n中取 r 个数作组合的问题可以分解成：先分别取这 n 个数中的一个数 i （只需要在前 n-r+1 个数中取 i ）；然后从