1、遞歸的概念與特征The concept and characteristics of recursion引 入“從前有座山，山上有座廟，廟里有個(gè)老和尚，老和尚在給小和尚講故事，故事講的是從前有座山，山上有座廟，廟里有個(gè)老和尚，老和尚在給小和尚講故事，”什么是遞歸What is recursion#01def f (n): if n=0: s=1 else: s=n*f(n-1) return sprint(f(3)下列程序段的輸出結(jié)果為_(kāi)。簡(jiǎn)述程序執(zhí)行過(guò)程這段程序有什么特點(diǎn)？當(dāng)主程序執(zhí)行函數(shù)f(3)時(shí)，引起第1次函數(shù)調(diào)用，進(jìn)入函數(shù)后，參數(shù)n=3，應(yīng)執(zhí)行計(jì)算3*f (2)。引起第2次函數(shù)調(diào)用，進(jìn)

2、入函數(shù)后，參數(shù)n=2，應(yīng)執(zhí)行計(jì)算2*fac(1)。直到計(jì)算fac(0)，將引起對(duì)函數(shù)f的第4次調(diào)用。遞歸的定義大問(wèn)題的解決中嵌套著與原問(wèn)題相似的規(guī)模較小的問(wèn)題。這種解決問(wèn)題的方式在計(jì)算機(jī)科學(xué)中稱為遞歸，通過(guò)函數(shù)自己調(diào)用自己來(lái)實(shí)現(xiàn)，即一個(gè)函數(shù)在其定義中直接或間接調(diào)用自身的一種方法。當(dāng)遞歸到達(dá)某個(gè)邊界，如問(wèn)題規(guī)?？s減為0或1時(shí)，能直接得解。因此，在設(shè)計(jì)遞歸算法時(shí)，要滿足兩個(gè)條件：確定遞歸公式和遞歸結(jié)束條件。def f (n): if n=0: s=1 else: s=n*f(n-1) return sprint(f(3)f (3)3*f (2)第1次調(diào)用第2次調(diào)用2*f(1)第3次調(diào)用1*f(0)

3、第4次調(diào)用1遞歸調(diào)用過(guò)程返回值1返回值1返回值2返回值6遞推回歸遞歸與棧遞歸公式使用遞歸解決的問(wèn)題都可以通過(guò)同一套規(guī)則轉(zhuǎn)化為比該問(wèn)題更為簡(jiǎn)單的子問(wèn)題，這套規(guī)則被稱為該問(wèn)題的遞歸公式。例如，在計(jì)算階乘問(wèn)題中， ()=()就是計(jì)算階乘的遞歸公式。遞歸結(jié)束條件經(jīng)過(guò)不斷縮小問(wèn)題規(guī)模，問(wèn)題最終能夠得以解決。在剛才的問(wèn)題中，的階乘經(jīng)過(guò)不斷簡(jiǎn)化，最終轉(zhuǎn)化為求解的階乘，而的階乘是我們已知的。 這種能直接得到結(jié)果，從而終止遞歸的情況，稱為遞歸的結(jié)束(邊界)條件。利用遞歸解決問(wèn)題Use recursion to solve problems#02問(wèn) 題problemAcademic reportpresentat

4、ion在迭代中，斐波那契數(shù)列指的是這樣一個(gè)數(shù)列: 1,1,2,3,5,8,13,21,34,.即從第3項(xiàng)開(kāi)始，每一項(xiàng)都是前面兩項(xiàng)的和。請(qǐng)根據(jù)同學(xué)們斐波那契數(shù)列的定義，用遞歸算法去求解斐波那契數(shù)列的第n項(xiàng)，編寫(xiě)計(jì)算斐波那契數(shù)列的程序， 并求出斐波那契數(shù)列第45項(xiàng)的結(jié)果，自定義函數(shù)名為fib。Coding is FUN分析問(wèn)題遞歸公式與遞歸條件：根據(jù)定義可知:ib()=ib()+ib(), 當(dāng) = 或者 = 的時(shí)候 ib() 為 ，此時(shí)直接返回結(jié)果就可以。程序編寫(xiě)def fib(n): if n=1 or n=2: return 1 else: return fib(n-1)+fib(n-2)pr

5、int(f(45)迭代程序遞歸程序f0=0f1=1n=2while nC二個(gè)盤子，2號(hào)：A-B 1號(hào)：A-C 2號(hào)：B-C三個(gè)盤子呢？n個(gè)盤子呢？將n-1個(gè)盤子從A柱經(jīng)過(guò)C柱移動(dòng)到B柱將A柱中剩下的一個(gè)盤子移動(dòng)到C柱將n-1個(gè)盤子從B柱經(jīng)過(guò)A柱移動(dòng)到C柱n-1個(gè)看成一個(gè)整體將n-1個(gè)盤子從A柱經(jīng)過(guò)C柱移動(dòng)到B柱將A柱中剩下的一個(gè)盤子移動(dòng)到C柱將n-1個(gè)盤子從B柱經(jīng)過(guò)A柱移動(dòng)到C柱【設(shè)計(jì)算法】（1）定義一個(gè)實(shí)現(xiàn)盤子移動(dòng)的函數(shù)move。如將n個(gè)盤子從A柱經(jīng)過(guò)B柱移動(dòng)到C柱，可調(diào)用函數(shù)move(n, a, b, c)，其中，n表示A柱上的盤子個(gè)數(shù)，a、b、c分別表示A柱、B柱、C柱。（3）當(dāng)n=1時(shí)，直接移動(dòng)盤子，遞歸結(jié)束。move(n-1, a, c, b)acmove(n-1, b, a, c)【程序?qū)崿F(xiàn)】def move(n,a,b,c): global s if n=1: s+=1 print(a,-,c,s) else: mov