(6.29)-第28课（6.4节-递归函数）C语言程序设计

递归函数函数函数的嵌套调用不允许嵌套定义函数，函数间的关系是平行的、独立的允许嵌套调用，即在调用某函数过程中又调用另一函数main()调用函数a结束a函数b函数调用函数b

【例1：】求三个数中最大数和最小数的差值#include<stdio.h>

intdif(intx,inty,intz);intmax(intx,inty,intz);

intmin(intx,inty,intz);voidmain(){inta,b,c,d;scanf("%d%d%d",&a,&b,&c);

d=dif(a,b,c);printf("Max-Min=%d\n",d);}intdif(intx,inty,intz){returnmax(x,y,z)-min(x,y,z);}intmax(intx,inty,intz){intr;r=x>y?x:y;return(r>z?r:z);}intmin(intx,inty,intz){intr;r=x<y?x:y;return(r<z?r:z);}main()调用函数dif输出结束dif函数max函数调用函数max调用函数minmin函数

⑩⑾⑿函数的递归调用在函数调用过程中，直接或间接的调用自身直接递归调用：在函数体内又调用自身间接递归调用：当函数1去调用另一函数2时，而另一函数2反过来又调用函数1自身f()调fintf(intx){inty,z;……

z=f(y);…….return(2*z);}直接递归调用调f2调f1f1()f2()intf1(intx){inty,z;……

z=f2(y);…….return(2*z);}intf2(intt){inta,c;……

c=f1(a);…….return(3+c);}间接递归调用【例2：】有5个人，第5个人比第4个人大2岁，第4个人比第3个人大2岁，……第2个人比第1个人大2岁，第1个人10岁，问第5个人多大？age(5)age(4)age(3)age(2)age(1)=2+age(4)=2+age(3)=2+age(2)=2+age(1)

递推回推=10=12=14=16=18数学模型10n=1age(n)=age(n-1)+2n>1#include<stdio.h>intage(intn){intc;if(n==1)c=10;elsec=2+age(n-1);return(c);}voidmain()

{printf(“%d\n”,age(5));}递归的本质将大问题的求解转化为较小问题的求解持续不断的分解过程最终将问题化简成一个最基本的形式（该形式是一个已知解）

条件成立，进行递归用if语句控制条件不成立，结束递归解决无终止递归调用的方法是：确定好结束递归的条件【例3：】用递归方法计算n!分析4!=4*3*2*14!=4*3!3!=3*2!......递归公式n!=1（n=0或1）n*(n-1)!

（n>1）#include<stdio.h>longfac(intn)

{longf;if(n==0||n==1)

f=1;elsef=n*fac(n-1);returnf;}voidmain(){printf("\n\t4!=%ld\n",fac(4));}f=fac(4);

n=4if(n==0||n==1)f=1;elsef=n*fac(n-1);return(f)n=3if(n==0||n==1)f=1;elsef=n*fac(n-1);return(f)n=2if(n==0||n==1)f=1;elsef=n*fac(n-1);return(f)n=1if(n==0||n==1)f=1;elsef=n*fac(n-1);return(f)

设n=44!递归结束条件244*3!6*43*2!2*1!12*31**21【例4：】求两个整数的最大公约数求最大公约数可以采用辗转相除法intgcd(inta,intb){ if(a%b==0)returnb; returngcd(b,a%b);}【例5：】使用递归算法生成斐波那契(Fibonacci)数列递归公式：f1=1(n=1)f2=1(n=2)fn=fn-1+fn-2(n≥3)intfib(intn){if(n<=2)

return1;else

returnfib(n-1)+fib(n-2);}【例6：】汉诺塔问题问题假设有三个分别命名为X，Y和Z的塔座，在塔座X上插有n个直径大小各不相同、依从小到大编号为1，2，…，n的圆盘。现要求将X轴上的n个圆盘移到塔座Z上，并按同样的顺序叠放移动时必须遵循以下规则：每次只能移动一个圆盘圆盘可以插在X，Y和Z中的任一塔座上任何时候都不能将一个较大的圆盘压在较小的圆盘之上XYZ汉诺塔问题分析n=1时将圆盘1从塔座X移到塔座ZXYZXYZ基本情形汉诺塔问题分析n>1时利用塔座Z为辅助塔座，将压在圆盘n之上的n-1个盘从塔座X移到塔座Y

（——与原问题类似）将圆盘n从塔座X移到塔座Z利用塔座X为辅助塔座，将塔座Y上的n-1个圆盘移动到塔座Z

（——与原问题类似）XYZXYZXYZXYZ汉诺塔问题设计move函数：移动一个盘-把盘n从s塔移到d塔hanoi函数：移动n个盘的汉诺塔问题-把n个盘从x塔移到z塔，y塔作为辅助塔voidmove(intn,chars,chard);voidhanoi(intn,charx,chary,charz);汉诺塔问题实现#include<stdio.h>voidmove(intn,chars,chard);voidhanoi(intn,charx,chary,charz);voidmain(){intn;printf("\tInputthenumberofdisks:");scanf("%d",&n);hanoi(n,'X','Y','Z');}voidhanoi(intn,charx,chary,charz){

if(n==1)move(n,x,z);else{hanoi(n-1,x,z,y);move(n,x,z);

hanoi(n-1,y,x,z