遞歸 【核心知識(shí) 精講精研】 浙教版（2019）高中信息技術(shù)選修1

5.2.2遞歸遞歸算法現(xiàn)在，我們把問題反過來(lái)思考f(5)=f(4)*5f(4)=f(3)*4f(3)=f(2)*3f(2)=f(1)*2f(1)=f(0)*1遞推問題逐漸縮小回歸大問題的解決中嵌套著與原問題相似的規(guī)模較小的問題。這種解決問題的方式在計(jì)算機(jī)科學(xué)中稱為遞歸，通過函數(shù)自己調(diào)用自己來(lái)實(shí)現(xiàn)，即一個(gè)函數(shù)在其定義中直接或間接調(diào)用自身的一種方法。遞歸算法1.大問題能分解成結(jié)構(gòu)相似且規(guī)模較少的問題，這些小問題的階可以方便地構(gòu)造出大問題的解；2.當(dāng)遞歸到達(dá)某個(gè)邊界時(shí)，當(dāng)遞歸到達(dá)某個(gè)邊界，如問題規(guī)?？s減為0或1時(shí)，能直接得解。這個(gè)邊界被稱為遞歸出口?！つ懿捎眠f歸算法解決的問題特征因此，在設(shè)計(jì)遞歸算法時(shí)，要滿足兩個(gè)條件：確定遞歸公式和遞歸結(jié)束條件。遞歸算法1（n=0）n*f(n-1)（n>0）f(n)5！=5*4！4！=4*3！3！=3*2！2！=2*1！1！=1*0！0！=1遞推：分解問題回歸：代值求解任務(wù)一：利用遞歸思想設(shè)計(jì)一個(gè)函數(shù)f，用來(lái)計(jì)算5的階乘deff(n):ifn==0:___________else:

___________returnff=1f=n*f(n-1)算法時(shí)間復(fù)雜度為：O(n)遞歸算法遞歸程序的執(zhí)行過程1.在遞推階段，把較復(fù)雜的問題的求解遞推到一些簡(jiǎn)單問題的求解。必須要有終止遞推的情況。2.在回歸階段，當(dāng)獲得最簡(jiǎn)單情況的解后，逐級(jí)返回依次得到稍復(fù)雜問題的解。遞歸算法1*fac(0)2*fac(1)3*fac(2)4*fac(3)5*fac(4)fac(1)fac(2)fac(3)fac(4)fac(5)通過不斷的調(diào)用自己縮小問題規(guī)模，進(jìn)而求解?？臻g復(fù)雜度大用棧實(shí)現(xiàn)遞歸：遞歸算法迭代：由舊值不斷推出新值的過程。它包括三個(gè)方面：①確定迭代變量；②建立迭代關(guān)系式；③控制迭代過程，使程序能夠停止下來(lái)。遞歸：是一種縮小問題規(guī)模，進(jìn)而構(gòu)造出整個(gè)問題解的思想方法。①遞推

②回歸迭代難點(diǎn)：建立正確的迭代公式，通常要借助循環(huán)語(yǔ)句。遞歸難點(diǎn)：思想比較難以理解，遞歸程序的效率相對(duì)不高。辨析迭代與遞歸：遞歸算法——漢諾塔游戲漢諾塔游戲漢諾塔游戲的裝置是一塊銅板，上面有三根針，其中最左側(cè)一根針上放著從大到小的n個(gè)圓盤。游戲的目標(biāo)是把所有的圓盤從最左側(cè)一根針上移動(dòng)到最右側(cè)一根針上，中間一根針作為過渡。游戲規(guī)定每次只能移動(dòng)一個(gè)圓盤，并且大盤子不能壓在小盤子上面。遞歸算法——漢諾塔游戲漢諾塔游戲啟始針A過渡針B目標(biāo)針C一個(gè)盤子:二個(gè)盤子:三個(gè)盤子呢？n個(gè)盤子呢？將n-1個(gè)盤子從A柱經(jīng)過C柱移動(dòng)到B柱將A柱中剩下的一個(gè)盤子移動(dòng)到C柱將n-1個(gè)盤子從B柱經(jīng)過A柱移動(dòng)到C柱n-1個(gè)看成一個(gè)整體A->C2號(hào)：A->B1號(hào)：A->C2號(hào)：B->C遞歸算法——漢諾塔游戲?qū)-1個(gè)盤子從A柱經(jīng)過C柱移動(dòng)到B柱將A柱中剩下的一個(gè)盤子移動(dòng)到C柱將n-1個(gè)盤子從B柱經(jīng)過A柱移動(dòng)到C柱【設(shè)計(jì)算法】1.定義一個(gè)實(shí)現(xiàn)盤子移動(dòng)的函數(shù)move。如將n個(gè)盤子從A柱經(jīng)過B柱移動(dòng)到C柱，可調(diào)用函數(shù)move(n,a,b,c)，

其中，n表示A柱上的盤子個(gè)數(shù)，a、b、c分別表示A柱、B柱、C柱。2.當(dāng)n=1時(shí)，直接移動(dòng)盤子，遞歸結(jié)束。move(n-1,a,c,b)move(1,a,b,c)move(n-1,b,a,c)遞歸算法——漢諾塔游戲defmove(n,a,b,c):if____________:print(a,"--->",c)else:move(n-1,a,c,b)move(1,a,b,c)

____________a=int(input("請(qǐng)輸入A柱盤子的個(gè)數(shù)："))print(f"把{a}個(gè)盤子全部移動(dòng)到C柱子的順序?yàn)椋?)move(a,"A","B","C")n==1move(n-1,b,a,c)遞歸算法——進(jìn)制轉(zhuǎn)換編寫程序，輸入兩個(gè)正整數(shù)x,y(y<=l6),實(shí)現(xiàn)將十進(jìn)制數(shù)x轉(zhuǎn)換為十六進(jìn)制y輸出。迭代程序defconvert(n,base):convert_s="0123456789ABCDEF"ans=""whilen>0:x=______________________________________n=n//basereturnansx=int(input("請(qǐng)輸入x："))y=int(input("請(qǐng)輸入y："))print(convert(x,y))n%baseans=convert_s[x]+ans遞歸算法——綜合應(yīng)用為了防止黑客惡意破解密碼、機(jī)器惡意注冊(cè)或刷票等不良行為,很多網(wǎng)絡(luò)平臺(tái)使用驗(yàn)證碼作為一種通行方式。小明給自己的網(wǎng)站平臺(tái)設(shè)計(jì)了如下驗(yàn)證碼功能:首先計(jì)算機(jī)隨機(jī)生成一個(gè)[1,100000]范圍內(nèi)的整數(shù)作為驗(yàn)證碼,用戶通過計(jì)算該整數(shù)各位數(shù)字的和并輸入驗(yàn)證,只有驗(yàn)證通過才能正常登錄。例如,若計(jì)算機(jī)產(chǎn)生的隨機(jī)數(shù)為21304,則用戶只有輸入10(2+1+3+0+4=10)才能正常登錄。遞歸算法——綜合應(yīng)用【算法分析】該驗(yàn)證碼功能需要從隨機(jī)數(shù)x中分解出各位數(shù)字并求和。由于隨機(jī)數(shù)x的位數(shù)不確定,而任何整數(shù)x的個(gè)位數(shù)一定可以通過x%10得到，剩下的(x//10)可以采用遞歸算法進(jìn)行分解。通過函數(shù)fenjie(x)先將x的各位數(shù)字分解并存入數(shù)組ans,再求得和sumx,最后將sumx與用戶輸入的信息進(jìn)行比對(duì),輸出響應(yīng)的提示信息，請(qǐng)完善以下代碼。遞歸算法——綜合應(yīng)用importrandomdeffenjie(x):ifx<10:ans.append(x)else:ys=x%10____________fenjie(x)ans.append(ys)x=random.randint(1,100000)print("隨機(jī)產(chǎn)生的整數(shù)為:",x)y=int(input("請(qǐng)輸入你的運(yùn)算結(jié)果:"))ans=[]fenjie(x)sumx=0foriinans:___________if_______________:print("驗(yàn)證通過!")else:print("輸入錯(cuò)誤!")x=x//10sumx+=isumx==y課堂小結(jié)遞歸的必要條件遞歸的適用情況遞歸的定義函數(shù)的遞歸調(diào)用是指一個(gè)函數(shù)在它的函數(shù)體內(nèi)，直接或間接地調(diào)用它自身，稱為遞歸調(diào)用。這種函數(shù)稱為遞歸函數(shù)。確定遞歸條件尋找遞歸出口問題在規(guī)模小時(shí)能夠直接得出答案可以通過同一套規(guī)則轉(zhuǎn)化為比該問題更為簡(jiǎn)單的子問題。練一練1.遞歸算法的函數(shù)調(diào)用時(shí)，處理參數(shù)和返回地址通常使用的數(shù)據(jù)結(jié)構(gòu)是（）A.數(shù)組B.隊(duì)列C.棧D.鏈表C練一練2.樓梯上有8級(jí)臺(tái)階，從下開始往上走，每次可以走一步或者兩步，自定義函數(shù)fg可以計(jì)算走完n級(jí)臺(tái)階有多少種走法。實(shí)現(xiàn)對(duì)應(yīng)功能的Python程序如下：deffg(n):ifn==1:return1elifn==2:return2e