第3讲_函数的递归调用VIP免费

第3讲函数的递归调用本讲内容：(1)递归函数的定义与调用(2)汉诺塔问题(3)分治法的基本思想(4)二分搜索技术递归的概念递归函数:直接调用自己或通过另一函数间接调用自己的函数用递归求解问题的特点(1)存在递归的终止条件(2)存在导致问题求解的递归方式1n=0,1n*(n-1)!n>0n!=递归的终止条件递归公式例:用递归的方法求n!1n=0,1n*(n-1)!n>1n!=递归的终止条件递归方式4!=4*(4-1)!返回值6返回值2返回值13!=3*(3-1)!2!=2*(2-1)!1!=1主调函数返回值24调用#includefloatfac(intn);voidmain(){intm;floaty;scanf(“%d”,&m);y=fac(m);/*调用函数fac()*/printf(“%d!=%15.0f\n”,m,y);}函数声明递归调用函数定义floatfac(intn){floatf;if(n<0){printf(“error!”);f=-1;}elseif(n==0||n==1)f=1;elsef=n*fac(n-1);/*递归调用自己*/return(f);}main函数输入m③y=fac(m)输出y⑥调用facmn③因3!=0,1f=3*fac(3-1)返回f⑥调用facmn②返回f②返回f①因2!=0,1f=2*fac(2-1)调用facmn①因1==1f=1结束递归调用过程:递归法求Fibonacci数列Fibonacci数列:1,1,2,3,5,8,13…迭代法求Fibonacci数列的前20项#includevoidmain(){inti,f1=1,f2=1,f3;printf(“%8d%8d”,f1,f2);for(i=3;i<=20;i++){f3=f1+f2;f1=f2;f2=f3;printf(“%8d”,f3);if(i%4==0)putchar(‘\n’);}}迭代法在已知数列前2项的基础上,从第3项开始,依次向后计算,得出数列的每一项思考:怎样用递归的方法求解？定义Fibonacci数列的递归数学模型：递归法求Fibonacci数列1n=0,1F(n-1)+F(n-2)n>1F(n)=递归的终止条件递归公式intFib(intn){if(n<0){printf(“error!”);exit(-1);}elseif(n<=1)return1;elsereturnFib(n-1)+Fib(n-2);}递归法求Fibonacci数列用递归法求Fibonacci数列Fib(4)return+Fib(3)Fib(2)return+Fib(1)Fib(0)return+Fib(2)Fib(1)return+Fib(1)Fib(0)return1return1return1return1return1递归法是从第n项开始向前计算,当n等于0或1时结束递归调用,开始返回112111235n=20时,要进行21891次递归调用思考:求Fibonacci数列的迭代法和递归法谁好？递归法求Fibonacci数列ABC一个黄铜板上，插着三根宝石针，其中一根针上从下到上放了由大到小的64块金片，这就是Hanoi塔。Hanoi塔问题：就是如何将64块金片按照梵天不渝法则，由一根宝石针全部移动到另一根宝石针上去。Hanoi问题Hanoi问题问题描述：设A,B,C是3个塔座。在塔座A上有n个圆盘,这些圆盘自下而上,由大到小的叠放。要求将A上的圆盘移到C上,并仍按同样顺序叠放。移动圆盘应遵守以下规则：规则1：每次只能移动1个圆盘规则2：任何时刻都不允许将大圆盘压在小圆盘之上规则3：在满足规则1和2的前提下,可将圆盘移至任一塔座上AABBCC3个圆盘的移动过程演示A→CA→BHanoi问题AABBCC3个圆盘的移动过程演示C→BHanoi问题AABBCC3个圆盘的移动过程演示A→CHanoi问题AABBCC3个圆盘的移动过程演示B→AB→CHanoi问题AABBCCn较大时怎么办？3个圆盘的移动过程演示A→Cn个圆盘需要2n-1次移动n=64时,需要264-1次移动，即1844亿亿次移动。若每次移动需用1微秒,则总共需要60万年时间！3个圆盘一共需要7次移动：A→C，A→B，C→B，A→C，B→A，B→C，A→CHanoi问题移动步骤：①(n-1)个圆盘AB②第n个圆盘AC③(n-1)个圆盘BCACCBn个圆盘的移动方法：n个圆盘分为2部分上面(n-1)个圆盘最下面的第n号圆盘(n-1)个圆盘怎么移动？递归何时结束？Hanoi问题第n个圆盘ACn=1(n-1)个圆盘AB第n个圆盘AC(n-1)个圆盘BCn>1voidHan(intn,intA,intB,intC){if(n==1)Move(n,A,C);else{Han(n-1,A,C,B);Move(n,A,C);Han(n-1,B,A,C);}}递归法求解hanoi问题//将n-1个盘子从A移到B,借助于C//将n-1个盘子从B移到C,借助于A//将第n个盘子从A移到C//将n个盘子从A移到C,借助于B//将1个盘子从A移到C请特别注意这3个参数的顺序Hanoi问题Han(3,A,B,C){if(n==1)Move(n,A,C);else{Han(2,A,C,B);Move(3,A,C);Han(2,B,A,C);}}Han(2,A,C,B){if(n==1)Move(n,A,B);else{Han(1,A,B,C);Move(2,A,B);Han(1,C,A,B);}}Han(1,A,B,C){if(n==1)Move(1,A,C);}Han(1,C,A,B){if(n==1)Move(1,C,B);}Ha...