第3講函數(shù)的遞歸調(diào)用

第3講函數(shù)的遞歸調(diào)用本講內(nèi)容：

(1)遞歸函數(shù)的定義與調(diào)用

(2)

漢諾塔問(wèn)題

(3)分治法的基本思想

(4)二分搜索技術(shù)

遞歸的概念遞歸函數(shù):直接調(diào)用自己或通過(guò)另一函數(shù)間接調(diào)用自己的函數(shù)用遞歸求解問(wèn)題的特點(diǎn)(1)存在遞歸的終止條件(2)存在導(dǎo)致問(wèn)題求解的遞歸方式1n=0,1n*(n-1)!n>0

n!=遞歸的終止條件遞歸公式例:用遞歸的方法求n!1n=0,1n*(n-1)!n>1

n!=遞歸的終止條件遞歸方式4!=4*(4-1)!

返回值6返回值2返回值13!=3*(3-1)!2!=2*(2-1)!1!=1主調(diào)函數(shù)返回值24調(diào)用#include<stdio.h>floatfac(intn);voidmain(){intm;floaty;

scanf(“%d”,&m);

y=fac(m);/*調(diào)用函數(shù)fac()*/

printf(“%d!=%15.0f\n”,m,y);}函數(shù)聲明遞歸調(diào)用函數(shù)定義floatfac(intn){floatf;if(n<0){printf(“error!”);f=-1;}elseif(n==0||n==1)f=1;elsef=n*fac(n-1);/*遞歸調(diào)用自己*/return(f);}main函數(shù)輸入m③y=fac(m)輸出y⑥調(diào)用facmn③

因

3!=0,1f=3*fac(3-1)返回f⑥調(diào)用facmn②返回f②返回f①

因

2!=0,1f=2*fac(2-1)調(diào)用facmn①因1==1f=1結(jié)束遞歸調(diào)用過(guò)程:遞歸法求Fibonacci數(shù)列Fibonacci數(shù)列:1,1,2,3,5,8,13…迭代法求Fibonacci數(shù)列的前20項(xiàng)#include<stdio.h>voidmain(){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’);}

}迭代法在已知數(shù)列前2項(xiàng)的基礎(chǔ)上,從第3項(xiàng)開始,依次向后計(jì)算,得出數(shù)列的每一項(xiàng)思考:怎樣用遞歸的方法求解？定義Fibonacci數(shù)列的遞歸數(shù)學(xué)模型：遞歸法求Fibonacci數(shù)列1n=0,1F(n-1)+F(n-2)n>1

F(n)=遞歸的終止條件遞歸公式int

Fib(intn){if(n<0){printf(“error!”);exit(-1);}else

if(n<=1)return1;elsereturnFib(n-1)+Fib(n-2);}遞歸法求Fibonacci數(shù)列用遞歸法求Fibonacci數(shù)列Fib(4)return+Fib(3)Fib(2)return+Fib(1)Fib(0)return+Fib(2)Fib(1)return+Fib(1)Fib(0)return1return1return1return1return1遞歸法是從第n項(xiàng)開始向前計(jì)算,當(dāng)n等于0或1時(shí)結(jié)束遞歸調(diào)用,開始返回112111235n=20時(shí),要進(jìn)行21891次遞歸調(diào)用思考:求Fibonacci數(shù)列的迭代法和遞歸法誰(shuí)好？遞歸法求Fibonacci數(shù)列一個(gè)黃銅板上，插著三根寶石針，其中一根針上從下到上放了由大到小的64塊金片，這就是Hanoi塔。Hanoi塔問(wèn)題：就是如何將64塊金片按照梵天不渝法則，由一根寶石針全部移動(dòng)到另一根寶石針上去。Hanoi問(wèn)題Hanoi問(wèn)題問(wèn)題描述：設(shè)A,B,C是3個(gè)塔座。在塔座A上有n個(gè)圓盤,這些圓盤自下而上,由大到小的疊放。要求將A上的圓盤移到C上,并仍按同樣順序疊放。移動(dòng)圓盤應(yīng)遵守以下規(guī)則：規(guī)則1：每次只能移動(dòng)1個(gè)圓盤規(guī)則2：任何時(shí)刻都不允許將大圓盤壓在小圓盤之上規(guī)則3：在滿足規(guī)則1和2的前提下,可將圓盤移至任一塔座上ABC3個(gè)圓盤的移動(dòng)過(guò)程演示A→CA→BHanoi問(wèn)題ABC3個(gè)圓盤的移動(dòng)過(guò)程演示C→BHanoi問(wèn)題ABC3個(gè)圓盤的移動(dòng)過(guò)程演示A→CHanoi問(wèn)題ABC3個(gè)圓盤的移動(dòng)過(guò)程演示B→AB→CHanoi問(wèn)題ABCn較大時(shí)怎么辦？3個(gè)圓盤的移動(dòng)過(guò)程演示A→Cn個(gè)圓盤需要2n-1次移動(dòng)n=64時(shí),需要264-1

次移動(dòng)，即1844億億次移動(dòng)。若每次移動(dòng)需用1微秒,則總共需要60萬(wàn)年時(shí)間！3個(gè)圓盤一共需要7次移動(dòng)：A→C，A→B，C→B，A→C，B→A，B→C，A→CHanoi問(wèn)題移動(dòng)步驟：①(n-1)個(gè)圓盤AB②第n個(gè)圓盤AC③(n-1)個(gè)圓盤BCACBn個(gè)圓盤的移動(dòng)方法：n個(gè)圓盤分為2部分上面(n-1)個(gè)圓盤最下面的第n號(hào)圓盤(n-1)個(gè)圓盤怎么移動(dòng)？遞歸何時(shí)結(jié)束？Hanoi問(wèn)題第n個(gè)圓盤ACn=1(n-1)個(gè)圓盤AB第n個(gè)圓盤AC(n-1)個(gè)圓盤BCn>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問(wèn)題//將n-1個(gè)盤子從A移到B,借助于C//將n-1個(gè)盤子從B移到C,借助于A//將第n個(gè)盤子從A移到C//將n個(gè)盤子從A移到C,借助于B//將1個(gè)盤子從A移到C請(qǐng)?zhí)貏e注意這3個(gè)參數(shù)的順序Hanoi問(wèn)題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);}Han(2,B,A,C){if(n==1)Move(n,B,C);else{

Han(1,B,C,A);

Move(2,B,C);Han(1,A,B,C);

}}Han(1,B,C,A){if(n==1)

Move(1,B,A);}Han(1,A,B,C){if(n==1)

Move(1,A,C);}

ABC

ABC

ABC

ABC

ABC

ABC

ABC

ABC遞歸與迭代遞歸與迭代都涉及循環(huán)迭代是顯示使用循環(huán)結(jié)構(gòu)遞歸通過(guò)重復(fù)調(diào)用函數(shù)實(shí)現(xiàn)循環(huán)遞歸與迭代都涉及終止測(cè)試迭代在循環(huán)條件為假時(shí)終止遞歸在滿足終止條件時(shí)結(jié)束遞歸與迭代都可以無(wú)限進(jìn)行迭代當(dāng)循環(huán)條件永真時(shí)形成無(wú)限循環(huán)遞歸如果無(wú)法到達(dá)終止條件則發(fā)生無(wú)窮遞歸遞歸與迭代有些問(wèn)題既可用迭代法求解，也可用遞歸法求解如：求n！，F(xiàn)ibonacci數(shù)列，求xn

等迭代法編程代碼相對(duì)比較復(fù)雜，但運(yùn)行效率高遞歸法編程結(jié)構(gòu)清晰，可讀性強(qiáng)，代碼簡(jiǎn)潔明了，但運(yùn)行效率很低遞歸和迭代的優(yōu)缺點(diǎn)有的問(wèn)題只能用遞歸法求解，如：漢諾塔問(wèn)題(n較大時(shí))遞歸法優(yōu)于迭代法之處在于它能更自然的反映問(wèn)題另外選擇遞歸的一個(gè)原因是可能沒(méi)有明顯的迭代方案課后作業(yè)課本P202：8.13，8.17分治法的基本思想分治法的思想:分而治之。將一個(gè)規(guī)模為n的問(wèn)題分解為k個(gè)規(guī)模較小的子問(wèn)題，這些子問(wèn)題互相獨(dú)立且與原問(wèn)題相同，(如果子問(wèn)題的規(guī)模仍然不夠小，則再劃分為k個(gè)子問(wèn)題),然后遞歸的求解這些子問(wèn)題，最后用適當(dāng)?shù)姆椒▽⒏髯訂?wèn)題的解合并成原問(wèn)題的解。原問(wèn)題(規(guī)模為n)子問(wèn)題1子問(wèn)題2子問(wèn)題k…子問(wèn)題1子問(wèn)題2子問(wèn)題k…相同類型合并解子問(wèn)題1子問(wèn)題2子問(wèn)題k…子問(wèn)題1子問(wèn)題2子問(wèn)題k…分治法的適用條件分治法所能解決的問(wèn)題一般具有以下幾個(gè)特征：該問(wèn)題的規(guī)模縮小到一定的程度就可以容易地解決該問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題該問(wèn)題所分解出的各個(gè)子問(wèn)題是相互獨(dú)立的利用分解出的子問(wèn)題的解可以合并為該問(wèn)題的解分治法的基本思想前提條件：有一組數(shù)已經(jīng)按從小到大(或從大到小)排序目標(biāo)：輸入一個(gè)數(shù)x，在這組數(shù)查找是否有x二分搜索的步驟：1、確定三個(gè)關(guān)鍵下標(biāo)的初值：bott=0,top=8,

mid=(bott+top)/2;2、判斷要找的數(shù)x是否等于a[mid]①x==a[mid]找到，結(jié)束x<a[mid]在a[bott]—a[mid-1]之間繼續(xù)查找x

top=mid-1;mid=(bott+top)/2;③x>a[mid]在a[mid+1]—a[top]之間繼續(xù)查找x

bott=mid+1;mid=(bott+top)/2;-15-6079235482101midbotttopa[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]二分搜索算法二分搜索實(shí)例:設(shè)在數(shù)組a中順序放了以下9個(gè)元素：檢索x=9,

9==a[4],一次比較就成功,

最好情況-15-6079235482101a[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]①②③③④②③④檢索x=-15,-15<a[4],-15<a[1],

-15==a[0],

3次比較,

成功檢索x=101,101>a[4],101>a[6],101>a[7],

101==a[8],

4次比較,

成功檢索x=8,8<a[4],8>a[1],8>a[2],8>a[3],4次比較,

不成功二分搜索算法#include<stdio.h>#defineN10int

find(inta[],intx,int

bott,inttop)；voidmain(){inti,x,a[N],result;

printf("\n

輸入數(shù)組a:\n");for(i=0;i<N;i++)scanf("%d",&a[i]);

printf(“輸入要查找的數(shù)