文档介绍：第十章递归程序设计递归设计递归执行递归——递归程序例10-1编一个函数factorial计算阶乘n!按过去程序设计思想,该函数应该写成:intfactorial(intn){inti,p;p=1;for(i=1;i<=n;i=i+1)p=p*i;returnp;}现在换一个角度考虑问题,n!不仅是 1*2*3*...*n还可以定义成n!=当n=0n*(n-1)!当n>0按照该定义,n!就是一个简单的条件语句和表达式计算,可以编出如下函数:intfactorial(intn){if(n==0)return1;else returnn*factorial(n-1);}问题:在函数factorial内又调用函数factorial本身,行吗?回答:行!首先按作用域规则,在函数factorial内又调用函数factorial本身是合法的;其次C系统保证上述调用过程执行的正确性,这就是递归。从静态行文看,在定义一个函数时,若在定义它的内部,又出现对它本身的调用,则称该函数是递归的,或递归定义的。从动态执行角度看,当调用一个函数时,在进入相应函数,还没退出(返回)之前,又再一次的调用它本身,而再一次进入相应函数,则称之为递归,或称之为对相应函数的递归调用。称递归定义的函数为递归函数。上述函数factorial就是递归函数。若计算5!,使用函数调用factorial(5),观察其计算过程:return5*f(4)f(5)f=120f(4)f(3)f(2)f(1)f(0)return4*f(3)return3*f(2)return2*f(1)return1*f(0)return1f=24f=6f=2f=1f=1intfactorial(intn){if(n==0)return1;else returnn*factorial(n-1);}voidmain(){printf(“%d\n”,f(5));}递归程序设计例10-2X的n次幂,可以定义为floatpower(floatx,intn){if(n==0)return1;elsereturnx*power(x,n-1);}例10-3n次勒让德多项式计算它的递归函数是:floatp(intn,floatx){if(n==0)return1;elseif(n==1)returnx;elsereturn((2*n-1)*x*p(n-1,x)-(n-1)*p(n-2,x))/n;}递归程序设计的思想体现在:用逐步求精原则,先把一个问题分解成若干子问题这些子问题中有问题的与原始问题具有相同的特征属性,至多不过是某些参数不同,规模比原来小了此时,就可以对这些子问题实施与原始问题同样的分析算法,直到规模小到问题容易解决或已经解决时为止。也就是说,若将整个问题的算法设计成一个函数,!的例子。该问题是:当n>0时,若能计算出w=(n-1)!则r=n!=n*w因此,得如下抽象算法::w=(n-1)!=n*w由于子算法1的特征属性与整个算法完全相同,只是参数不同,w代替了r,n-1代替了n。这时若将整个算法表示为f(n,r)则子算法1就是f(n-1,w)即是对f的递归调用。再考虑n=0时,这时r=0!=1,从而得到计算n!的函数fact。voidfact(intn,int*r){intw;if(n==0)*r=1;else{factorial(n-1,&w);*r=n*w}}若把该函数的参数r用函数值表示,就是前边的函数factorial。这里讲的只是一般规律和程序设计思想。实际使用时,设计递归函数要复杂得多。编写递归程序要注意:递归程序漂亮、好看、好读、风格优美,但执行效率低。计算n!的函数即可以写成循环形式,也可以写成递归形式。但是有些循环程序写成递归很困难。反之,有些递归程序写成循环也很困难,甚至是不可能的。终结条件。程序一定要能终止,不能无限递归下去。使用全局量要特别小心。用不好,单元发生冲突,将导致程序出错。