第8講B-遞歸函數(shù)市賽課一等獎(jiǎng)全省微課優(yōu)質(zhì)課特等獎(jiǎng)PPT課件省名師優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

遞歸函數(shù)/11/261/56一個(gè)經(jīng)過(guò)重復(fù)將問(wèn)題分解為同類(lèi)子問(wèn)題從而處理問(wèn)題方法“Thepowerofrecursionevidentlyliesinthepossibilityofdefininganinfinitesetofobjectsbyafinitestatement.Inthesamemanner,aninfinitenumberofcomputationscanbedescribedbyafiniterecursiveprogram,evenifthisprogramcontainsnoexplicitrepetitions.”NiklausWirth遞歸2/56階乘n!=n*(n-1)!Fibonacci數(shù)列

f(n)=f(n-1)+f(n-2)…什么問(wèn)題適合遞歸處理？3/56函數(shù)遞歸調(diào)用在調(diào)用一個(gè)函數(shù)過(guò)程中又出現(xiàn)直接或間接地調(diào)用該函數(shù)本身，稱(chēng)為函數(shù)遞歸調(diào)用。4/56f2函數(shù)調(diào)用f1函數(shù)函數(shù)遞歸調(diào)用f函數(shù)調(diào)用f函數(shù)f1函數(shù)調(diào)用f2函數(shù)直接調(diào)用本函數(shù)間接調(diào)用本函數(shù)5/56函數(shù)遞歸調(diào)用

例7.6有5個(gè)學(xué)生坐在一起問(wèn)第5個(gè)學(xué)生多少歲？他說(shuō)比第4個(gè)學(xué)生大2歲問(wèn)第4個(gè)學(xué)生歲數(shù)，他說(shuō)比第3個(gè)學(xué)生大2歲問(wèn)第3個(gè)學(xué)生，又說(shuō)比第2個(gè)學(xué)生大2歲問(wèn)第2個(gè)學(xué)生，說(shuō)比第1個(gè)學(xué)生大2歲最終問(wèn)第1個(gè)學(xué)生，他說(shuō)是10歲請(qǐng)問(wèn)第5個(gè)學(xué)生多大6/56函數(shù)遞歸調(diào)用解題思緒：要求第５個(gè)年紀(jì)，就必須先知道第４個(gè)年紀(jì)要求第４個(gè)年紀(jì)必須先知道第３個(gè)年紀(jì)第３個(gè)年紀(jì)又取決于第２個(gè)年紀(jì)第２個(gè)年紀(jì)取決于第１個(gè)年紀(jì)每個(gè)學(xué)生年紀(jì)都比其前１個(gè)學(xué)生年紀(jì)大２7/567.6函數(shù)遞歸調(diào)用解題思緒：age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=108/56age(5)=age(4)+2age(4)=age(3)+2age(3)=age(2)+2age(2)=age(1)+2age(1)=10age(2)=12age(3)=14age(4)=16age(5)=18

遞歸邊界9/56#include<stdio.h>intage(intn);intmain(){printf("NO.5,age:%d\n",age(5));return0;}

intage(intn){intc;if(n==1)c=10;elsec=age(n-1)+2;return(c);}10/56age(5)輸出age(5)mainc=age(4)+2age函數(shù)n=5c=age(3)+2age函數(shù)n=4c=age(1)+2age函數(shù)n=2c=age(2)+2age函數(shù)n=3c=10age函數(shù)n=1age(1)=10age(2)=12age(3)=14age(4)=16age(5)=181811/56例7.7用遞歸方法求ｎ！。解題思緒：求ｎ！能夠用遞推方法：即從１開(kāi)始，乘２，再乘３……一直乘到ｎ。遞推法特點(diǎn)是從一個(gè)已知事實(shí)(如1!=1)出發(fā)，按一定規(guī)律推出下一個(gè)事實(shí)(如2!=1!*2)，再?gòu)倪@個(gè)新已知事實(shí)出發(fā)，再向下推出一個(gè)新事實(shí)(3!=3*2!)。n!=n*(n-1)!。12/56例7.7用遞歸方法求ｎ！。解題思緒：求ｎ！也能夠用遞歸方法，即５！等于４！×５，而４！＝３！×４…，１?。剑笨捎孟旅孢f歸公式表示：13/56#include<stdio.h>intfac(intn);intmain(){intn=0;inty=0;printf("inputanintegernumber:");scanf("%d",&n);y=fac(n);printf("%d!=%d\n",n,y);return0;}14/56intfac(intn){intf;if(n<0) printf("n<0,dataerror!");elseif(n==0||n==1) f=1;elsef=fac(n-1)*n;returnf;}注意溢出15/56fac(5)輸出fac(5)mainf=fac(4)×5fac函數(shù)n=5f=fac(3)×4fac函數(shù)n=4f=fac(1)×2fac函數(shù)n=2f=fac(2)×3fac函數(shù)n=3f=1fac函數(shù)n=1fac(1)=1fac(2)=2fac(3)=6fac(4)=24fac(5)=12012016/56

例7.8漢諾塔（Hanoitower）問(wèn)題。古代有一個(gè)梵塔，塔內(nèi)有3個(gè)座A、B、C，開(kāi)始時(shí)Ａ座上有64個(gè)盤(pán)子，盤(pán)子大小不等，大在下，小在上。有一個(gè)老和尚想把這64個(gè)盤(pán)子從Ａ座移到Ｃ座，但要求每次只允許移動(dòng)一個(gè)盤(pán)，且在移動(dòng)過(guò)程中在3個(gè)座上都一直保持大盤(pán)在下，小盤(pán)在上。在移動(dòng)過(guò)程中能夠利用B座。要求編程序輸出移動(dòng)盤(pán)子步驟。17/5664個(gè)盤(pán)子從A座移動(dòng)到C座，需要移動(dòng)大約264

次盤(pán)子，每1秒移動(dòng)1次，則需約5840億年18/56思緒：假如有另外一個(gè)和尚能有方法將上面63個(gè)盤(pán)子從一個(gè)座移到另一座。那么，問(wèn)題就處理了。此時(shí)老和尚只需這么做：19/56轉(zhuǎn)化為遞歸形式：(1)命令第2個(gè)和尚將63個(gè)盤(pán)子從A座移到B座(2)自己將1個(gè)盤(pán)子（最底下、最大盤(pán)子）從A座移到C座(3)再命令第2個(gè)和尚將63個(gè)盤(pán)子從B座移到C座20/56ABC……將63個(gè)從A到B第1個(gè)和尚做法21/56……ABC讓第2個(gè)和尚將63個(gè)從A到B第1個(gè)和尚做法22/56……ABC自己將1個(gè)從A到C第1個(gè)和尚做法23/56……ABC自己將1個(gè)從A到C第1個(gè)和尚做法24/56……ABC讓第2個(gè)和尚將63個(gè)從B到C第1個(gè)和尚做法25/56……ABC讓第2個(gè)和尚將63個(gè)從B到C第1個(gè)和尚做法26/56ABC……將62個(gè)從A到C第2個(gè)和尚做法27/56ABC……讓第3個(gè)和尚將62個(gè)從A到C第2個(gè)和尚做法28/56ABC……自己將1個(gè)從A到B第2個(gè)和尚做法29/56ABC……自己將1個(gè)從A到B第2個(gè)和尚做法30/56ABC……讓第3個(gè)和尚將62個(gè)從C到B第2個(gè)和尚做法31/56ABC……讓第3個(gè)和尚將62個(gè)從C到B第2個(gè)和尚做法32/56第3個(gè)和尚做法第4個(gè)和尚做法第5個(gè)和尚做法第6個(gè)和尚做法第7個(gè)和尚做法……第63個(gè)和尚做法第64個(gè)和尚僅做：將1個(gè)從A移到C33/56ABC將3個(gè)盤(pán)子從A移到C全過(guò)程將2個(gè)盤(pán)子從A移到B34/56ABC將3個(gè)盤(pán)子從A移到C全過(guò)程將2個(gè)盤(pán)子從A移到B35/56ABC將3個(gè)盤(pán)子從A移到C全過(guò)程將1個(gè)盤(pán)子從A移到C36/56ABC將3個(gè)盤(pán)子從A移到C全過(guò)程將1個(gè)盤(pán)子從A移到C37/56ABC將3個(gè)盤(pán)子從A移到C全過(guò)程將2個(gè)盤(pán)子從B移到C38/56ABC將3個(gè)盤(pán)子從A移到C全過(guò)程將2個(gè)盤(pán)子從B移到C39/56ABC將2個(gè)盤(pán)子從A移到B過(guò)程將1個(gè)盤(pán)子從A移到C40/56ABC將2個(gè)盤(pán)子從A移到B過(guò)程將1個(gè)盤(pán)子從A移到C41/56ABC將2個(gè)盤(pán)子從A移到B過(guò)程將1個(gè)盤(pán)子從A移到B42/56ABC將2個(gè)盤(pán)子從A移到B過(guò)程將1個(gè)盤(pán)子從A移到B43/56ABC將2個(gè)盤(pán)子從A移到B過(guò)程將1個(gè)盤(pán)子從C移到B44/56ABC將2個(gè)盤(pán)子從A移到B過(guò)程將1個(gè)盤(pán)子從C移到B45/56ABC將2個(gè)盤(pán)子從B移到C過(guò)程46/56ABC將2個(gè)盤(pán)子從B移到C過(guò)程47/56ABC將2個(gè)盤(pán)子從B移到C過(guò)程48/56ABC將2個(gè)盤(pán)子從B移到C過(guò)程49/56由上面分析可知：將n個(gè)盤(pán)子從A座移到C座能夠分解為以下3個(gè)步驟：(1)將A上n-1個(gè)盤(pán)借助C座先移到B座上(2)把A座上剩下一個(gè)盤(pán)移到C座上(3)將n-1個(gè)盤(pán)從B座借助于Ａ座移到C座上50/56能夠?qū)⒌?1)步和第(3)步表示為：將“one”座上n-1個(gè)盤(pán)移到“two”座(借助“three”座)。在第(1)步和第(3)步中，one、two、three和A、B、C對(duì)應(yīng)關(guān)系不一樣。對(duì)第(1)步，對(duì)應(yīng)關(guān)系是one對(duì)應(yīng)A，two對(duì)應(yīng)B，three對(duì)應(yīng)C。對(duì)第(3)步，對(duì)應(yīng)關(guān)系是one對(duì)應(yīng)B，two對(duì)應(yīng)C，three對(duì)應(yīng)A。51/56把上面3個(gè)步驟分成兩類(lèi)操作：(1)將n-1個(gè)盤(pán)從一個(gè)座移到另一個(gè)座上（n＞1）。這就是大和尚讓小和尚做工作，它是一個(gè)遞歸過(guò)程，即和尚將任務(wù)層層下放，直到第64個(gè)和尚為止。(2)將1個(gè)盤(pán)子從一個(gè)座上移到另一座上。這是大和尚自己做工作。52/56編寫(xiě)程序。用hanoi函數(shù)實(shí)現(xiàn)第1類(lèi)操作（即模擬小和尚任務(wù)）用move函數(shù)實(shí)現(xiàn)第2類(lèi)操作（模擬大和尚自己移盤(pán)）函數(shù)調(diào)用hanoi(n,one,two.three)表示將n個(gè)盤(pán)子從“one”座移到“three”座過(guò)程(借助“two”座)函數(shù)調(diào)用move(x,y)表示將1個(gè)盤(pán)子從x座移到y(tǒng)座過(guò)程。x和y是代表A、B、C座之一，依據(jù)每次不一樣情況分別取A、B、C代入53/56#include<stdio.h>intmain(){voidhanoi(intn,charone,chartwo,charthree);intm;printf(“thenumberofdiskes:");scanf("%d",&m);printf("move%ddiskes:\n",m);

hanoi(m,'A','B','C');}54/56voidhanoi(intn,charone,chartwo,charthree){