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

5.2.2遞歸大問題的解決中嵌套著與原問題相似的規(guī)模較小的問題。這種解決問題的方式在計算機科學(xué)中稱為遞歸，通過函數(shù)自己調(diào)用自己來實現(xiàn)，即一個函數(shù)在其定義中直接或間接調(diào)用自身的一種方法。遞歸的作用：

能使函數(shù)的定義和算法的描述簡潔且易于理解，極大地減少程序代碼量。能采用遞歸描述的算法通常有這樣的特征：

為求解規(guī)模為N的問題，設(shè)法將它分解成規(guī)模較小的問題，然后從這些小問題的解中方便地構(gòu)造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，遞歸核心整體方法和局部方法是一致的。在設(shè)計遞歸算法時，要滿足兩個條件：確定遞歸公式和遞歸結(jié)束條件。例：利用遞歸算法求n的階乘（n!=1*2*…*n）。由數(shù)學(xué)知識可知，n階乘的遞歸定義為：它等于n乘以n-1的階乘，即n!=n*(n-1)!，并且規(guī)定0!=1。設(shè)函數(shù)fac(n)=n!，則fac(n)可表示為：fac(n)=1(n=0)n*fac(n-1)(n>0)按照這個公式，可以將求n!的問題轉(zhuǎn)化成求(n-1)!的問題；而求(n-1)!的問題，又可以轉(zhuǎn)化成求(n-2)!的問題；求（n-2）!的問題，又可以轉(zhuǎn)化成求(n-3)的問題，如此繼續(xù)，直到最后轉(zhuǎn)化成求0！的問題。再反過來，依次求出1！，2！，…，直到最后求出n!。因此，在該問題中，遞歸公式是fac(n)=n*fac(n-1),當(dāng)n=0時遞歸結(jié)束。求n的階乘的相應(yīng)的程序及測試結(jié)果如下：deffac(n):ifn==0:s=1else:s=n*fac(n-1)returnsprint(fac(3))當(dāng)主程序執(zhí)行函數(shù)fac(3)時，引起第1次函數(shù)調(diào)用，進入函數(shù)后，參數(shù)n=3，應(yīng)執(zhí)行計算3*fac(2)。直到計算fac(0)，將引起對函數(shù)fac的第4次調(diào)用。以上調(diào)用的執(zhí)行和返回情況，如下圖所示。fac(3)3*fac(2)第1次調(diào)用第2次調(diào)用2*fac(1)第3次調(diào)用1*fac(0)第4次調(diào)用1遞歸調(diào)用過程返回值1返回值1返回值2返回值6遞推回歸對于階乘問題，可以在原程序上通過添加一條語句來跟蹤參數(shù)n的變化情況：deffac(n):ifn==0:s=1else:print(str(n)+‘*fac(‘+str(n-1)+’)’)s=n*fac(n-1)returnsprint(fac(3))3*fac(2)2*fac(1)1*fac(0)6例.斐波那契數(shù)列是這樣一個數(shù)列：1,1,2,3,5,8,13,21,34，…，其定義如下：f(n)=f(n-1)+f(n-2)(n>=2)編程求f(n)的值，請分別用迭代和遞歸算法實現(xiàn)，并分析這兩種算法的時間復(fù)雜度。迭代程序遞歸程序n=int(input("請輸入正整數(shù):"))a=b=1foriinrange(3,n+1):______________________________print(c)

deffib(n):ifn<1:

________elifn==1:

__________else:

_________________n=int(input("請輸入正整數(shù):"))print(fib(n))c=a+ba=bb=creturn0return1returnfib(n-1)+fib(n-2)時間復(fù)雜度為O(n)fib(5)fib(3)fib(4)fib(3)fib(2)fib(2)fib(1)fib(1)fib(1)fib(1)fib(0)fib(2)fib(1)fib(0)fib(1)fib(5)遞歸調(diào)用的二叉樹表示遞歸調(diào)用次數(shù)即為二叉樹的節(jié)點個數(shù)（深度為n的二叉樹最多有_____個節(jié)點），即時間復(fù)雜度為______。O(2n)2n-1例.樓梯上有8級臺階，從下開始往上走，每次可以走一步或者兩步，自定義函數(shù)fg可以計算走完n級臺階有多少種走法。實現(xiàn)對應(yīng)功能的Python程序如下：deffg(n):ifn==1:return1elifn==2:return2else:returnfg(n-1)+fg(n-2)Print(‘走完8級臺階的方法共有’，fg(8)，‘種’)則走完這8級臺階的走法有（）A.34種B.35種C.36種D.37種A利用迭代和遞歸思想解決問題時有何區(qū)別？算法實現(xiàn)時兩者有哪些優(yōu)缺點？迭代的思想，是一種由舊值不斷推出新值的過程。它包括三個方面：一、確定迭代變量；二、建立迭代關(guān)系式；三、控制迭代過程，使程序能夠停止下來。遞歸思想，是一種把數(shù)據(jù)規(guī)模較大、較復(fù)雜的問題分解成規(guī)模較小的問題，進而構(gòu)造出整個問題解的思想方法。遞歸算法的執(zhí)行過程分__________兩個階段，其中的關(guān)鍵是如何建立遞歸關(guān)系式與控制程序停止。一般而言，迭代思想實現(xiàn)的難點在于建立正確的__________，通常要借助循環(huán)語句。而遞歸思想比較難以理解，程序編寫簡潔，但遞歸程序的效率_______________。遞推和回歸迭代公式相對不高例.遞歸算法的函數(shù)調(diào)用時，處理參數(shù)和返回地址通常使用的數(shù)據(jù)結(jié)構(gòu)是（）A.數(shù)組B.隊列C.棧D.鏈表C漢諾塔游戲1.抽象與建模選擇IDLE中的Help菜單——TurtleDemo——Minimal_Hanoi為了將n個盤子從A柱經(jīng)過B柱移動到C柱，可建立如下模型：將n-1個盤子從A柱經(jīng)過C柱移動到B柱將A柱中剩下的一個盤子移動到C柱將n-1個盤子從B柱經(jīng)過A柱移動到C柱漢諾塔游戲2.設(shè)計算法（1）定義一個實現(xiàn)盤子移動的函數(shù)move。如將n個盤子從A柱經(jīng)過B柱移動到C柱，可調(diào)用函數(shù)move(n,a,b,c)，其中，n表示A柱上的盤子個數(shù)，a、b、