《C语言程序设计吉林大学课件》由会员分享，可在线阅读，更多相关《C语言程序设计吉林大学课件（69页珍藏版）》请在金锄头文库上搜索。
1、第十章 递归程序设计,递归设计 递归执行,递归递归程序,例10-1 编一个函数 factorial 计算阶乘 ! 按过去程序设计思想，该函数应该写成： int factorial ( int n ) int i,p; p=1; for ( i=1 ; i=n ; i=i+1 ) p=p*i; return p ; ,现在换一个角度考虑问题，! 不仅是 1*2*3* . *n 还可以定义成,按照该定义，! 就是一个简单的条件语句和表达式计算， 可以编出如下函数： int factorial ( int n ) if ( n=0 ) return 1; else return n*factoria
2、l(n-1); ,问题：在函数 factorial 内又调用函数 factorial 本身，行吗？ 回答：行！ 首先按作用域规则，在函数 factorial 内又调用函数 factorial 本身是合法的；其次 C 系统保证上述调用过程执行的正确性，这就是递归。 从静态行文看，在定义一个函数时，若在定义它的内部，又出现对它本身的调用，则称该函数是递归的，或递归定义的。 从动态执行角度看，当调用一个函数时，在进入相应函数，还没退出（返回）之前，又再一次的调用它本身，而再一次进入相应函数，则称之为递归，或称之为对相应函数的递归调用。 称递归定义的函数为递归函数。 上述函数 factorial 就是
3、递归函数。若计算 5! ，使用函数调用factorial(5) ，观察其计算过程:,return 5*f(4),f(5),f=120,f(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 1,f=24,f=6,f=2,f=1,f=1,int factorial ( int n ) if ( n=0 ) return 1; else return n*factorial(n-1); void main() printf(“%dn”,f(5) ); ,递归程序设计,例10-2
4、X 的 n 次幂，可以定义为,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、题中有问题的与原始问题具有相同的特征属性，至多不过是某些参数不同，规模比原来小了 此时，就可以对这些子问题实施与原始问题同样的分析算法，直到规模小到问题容易解决或已经解决时为止。 也就是说，若将整个问题的算法设计成一个函数，则解决这个子问题的算法就表现为对相应函数的递归调用.,再看 n! 的例子。该问题是：当n0 时，若能计算出 w=(n-1)! 则 r=n!=n*w 因此，得如下抽象算法： 1. 计算：w=(n-1)! 2. r=n*w 由于子算法 1 的特征属性与整个算法完全相同，只是参数不同，w 代替了 r ，n-1 代替了 n 。这时若将整个算法表示为 f( n,r ) 则子算法 1
6、就是 f( n-1,w ) 即是对f的递归调用。 再考虑n=0时，这时r=0!=1 ，从而得到计算 n! 的函数fact 。,void fact ( int n , int *r ) int w ; if ( n=0 ) *r = 1 ; else factorial(n-1, *r = n*w ,若把该函数的参数r用函数值表示，就是前边的函数factorial 。,这里讲的只是一般规律和程序设计思想。实际使用时，设计递归函数要复杂得多。编写递归程序要注意： 递归程序漂亮、好看、好读、风格优美，但执行效率低。 计算! 的函数即可以写成循环形式，也可以写成递归形式。但是有些循环程序写成递归很困难
7、。反之，有些递归程序写成循环也很困难，甚至是不可能的。 终结条件。程序一定要能终止，不能无限递归下去。 使用全局量要特别小心。用不好，单元发生冲突，将导致程序出错。,例10-4汉诺（ Hanoi ）塔游戏,该问题又称世界末日问题。相传，古印度布拉玛婆罗门神庙的憎侣们，当时作一种被称为 Hanoi塔的游戏。该游戏是：在一个平板上，有三根钻石针；在其中一根针上有成塔型落放的大小不等的64片金片；要求把这64片金片全部移到另一根钻石针上。移动规则是： 每次只允许移动一片金片； 移动过程中的任何时刻，都不允许有较大的金片放在较小的金片的上面； 移动过程中，三根钻石针都可以利用，但是金片不许放在除钻石针
8、以外的任何地方。 不论白天黑夜都有一个憎侣在移动。据说当64片金片全部从一根钻石针移到另一根钻石针上那天，就是世界的末日。到那时他们的虔诚信徒可以升天，而其他人则要下地狱。,当然这只是传说，按照规则把 64 片金片全部从一根针移到另一根针上，总的移动次数是 264-1次，若一秒移动一次，不发生错误，日夜不停的移动，约需 5849 亿年。而太阳系的寿命仅有100150亿年而已。,请编程序，打印金片的移动顺序。,解：不妨设三根钻石针顺次编号为 a 、b 、c ；开始所有 64 片金片全部在 a 针上；现在要把它们移动到 b 针上；移动过程中 c 针可以利用。如图所示,a b c,试想，若能够把a
9、针上的64片金片全部移动到b针上，必须能够先把a针顶部的63片金片移到c针上。 现在，可以很容易的把a针上的一片金片移到 b 针上。 最后，再按照把a针上的63片金片移到c针上的算法，把c针上的63片金片全部移到b针上。从而，完成了题目要求的工作。 重新观察上述过程：,怎样进行移动？ 开始就遇到把a针最上边的金片先移到b针上，还是先移到c针上？没有任何根据作出决定，按一般方法是不好解决这个问题的。 下边换一个角度来考虑该问题：,按这个想法，移动 64 片金片的问题可以被分解成： 把a针上63片金片，从a针移到c针上，移动过程中b针可用； 把a针上一片金片移到b针上； 把c针上63片金片，从c针
10、移到b针上，移动过程中a针可用。 到此，问题虽然没有解决，但是已经向解的方向前进了一步，移动64 片金片的问题变成移动 63 片金片的问题了。这一步虽然很小, 甚至是微不足道的，但是却是十分重要的。,a b c,设若有一函数 move( n , x , y , z ) 能够完成：“把 x 针上的 n 片金片，移动到 y 针上，移动过程中可以利用 z 针。”， 则上述原始问题可以描述成对 move 的调用： move( 64 , a , b , c ) move( 63 , a , c , b ) move( 63 , c , b , a ),考虑move函数: 按分解移动 64 片金片问题的思
11、路，问题： “把x针上的n片金片，移动到y针上，移动过程中z针可用”可被分解成： 把 x 针上 n-1 片金片，从 x 针移到 z 针，移动过程中 y 针可用 把 x 针上一片金片移到 y 针上； 把 z 针上 n-1 片金片，从 z 针移到 y 针，移动过程中 x 针可用 按该分解算法，并考虑递归出口 (显然，当移动金片的片数为 0 时，便不用移动了)，最后得到完整的 Hanoi 塔解法程序如下,void moveone ( char u , char v ) printf ( “%c - %cn” , u , v ); void move ( int n, char x, char y,
12、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” , move ( n , a , b , c ) ,执行 hanoi 程序时不要输入太大的 n ，我们执行该程序。,执行主程序： 1、输出提示信息； 2、要求输入金片个数 n ，设输入“3”； 3、调用move函数：进入move ；n=30， 参数替换后，实际,printf( “pleace input n:”); sc
13、anf( “%d” , 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” , move ( n , a , b , c ),move
14、( 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 ( 1 , a , b , c )： 调用move函数：进入move ；n=10，执行 参数替换后，实际是执行：,printf( “pleace input n:”); scanf( “%d” ,
15、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( 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
16、, b )： 调用move函数，进入move ；n=0，返回。 调用moveone ，打印“a-b” 调用move函数，进入move ；n=0，返回。 move函数执行结束，返回。,printf( “pleace input n:”); scanf( “%d” , 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 ); move
