什么是Python的遞歸函數(shù)

• 1.遞歸的形象解釋
• 2.定義
• 3.步驟
• 4.終止條件
• 5.優(yōu)點(diǎn)
• 6.缺點(diǎn)
• 7.調(diào)用深度
• 8.課堂實(shí)例
• 9.計(jì)算n的階乘
  • 9.1什么是階乘
  • 9.2計(jì)算5！

1.遞歸的形象解釋

我們首先看一段視頻，來形象理解什么是遞歸。

視頻作者：pipi的奇思妙想

大家可以網(wǎng)上搜一下該作者的視頻，搜不到的可以聯(lián)系我！

【目標(biāo)任務(wù)】

電影院里，小玩偶想知道自己的位置在第幾排。

2.定義

一個(gè)函數(shù)是可以調(diào)用另一函數(shù)的。

作為特例，如果一個(gè)函數(shù)調(diào)用了自己，那我們稱這個(gè)函數(shù)為遞歸函數(shù)。

【示例】

f(x)=f(x+1)+x

f(x)和f(x+1)的函數(shù)名都是f，只是參數(shù)不同，一個(gè)是x，一個(gè)是x+1。

像這樣自己調(diào)用自己的表達(dá)式就是一個(gè)遞歸函數(shù)。

3.步驟

遞歸通?？梢苑譃閮刹剑合冗f后回歸。

視頻中的小玩偶從后往前詢問前一個(gè)小玩偶的坐位數(shù)，就是一個(gè)遞推的過程。

小玩偶從前往后告訴后一個(gè)小玩偶的它座位數(shù)，就是一個(gè)回歸的過程。

4.終止條件

遞歸函數(shù)必須有終止條件。

編程中，函數(shù)的調(diào)用要占用名叫棧(stack)的內(nèi)存空間。

調(diào)用函數(shù)時(shí)，程序會將相關(guān)的數(shù)據(jù)存儲到計(jì)算機(jī)的棧里。

當(dāng)函數(shù)運(yùn)行結(jié)束時(shí)數(shù)據(jù)會從棧里取出。

如果函數(shù)調(diào)用永遠(yuǎn)不停止，棧會被塞滿，數(shù)據(jù)就沒地方存儲。

我們將這種情況稱為棧溢出。

棧溢出，程序會被操作系統(tǒng)強(qiáng)行終止。

因此，遞歸函數(shù)必須有終止條件。

5.優(yōu)點(diǎn)

遞歸函數(shù)自己調(diào)用自己，代碼相對簡單。

6.缺點(diǎn)

遞歸函數(shù)每調(diào)用一次都會開相應(yīng)的內(nèi)存空間，因此遞歸函數(shù)的缺點(diǎn)就是占用內(nèi)存較多。

7.調(diào)用深度

遞歸調(diào)用的次數(shù)，我們稱之為調(diào)用深度。

遞歸函數(shù)調(diào)用深度是有限制的，超出會有溢出。

8.課堂實(shí)例

我們用一個(gè)簡單的例子來體驗(yàn)遞歸函數(shù)：

def f(x) :    
    return f(x-1)+x          
print(f(3))

【代碼解析】

1. 定義函數(shù)f，參數(shù)是x，注意自定義函數(shù)語句以英文冒號:結(jié)尾；
2. 自定義函數(shù)要實(shí)現(xiàn)的功能是：返回f(x-1)+x

f(x)和f(x-1)函數(shù)名相同，只是參數(shù)不同。

因此，在自定義函數(shù)f(x)中，它自己調(diào)用了自己。

3. 最后是調(diào)用函數(shù)，調(diào)用函數(shù)的語法為函數(shù)名(參數(shù))

這里的函數(shù)名是f，要傳入的實(shí)際參數(shù)為3。

【參數(shù)傳遞過程】

當(dāng)參數(shù)等于3的時(shí)候，函數(shù)的返回值是f(2)+3

3是確定的數(shù)值，f(2)的值無法確定，需要繼續(xù)調(diào)用函數(shù)。

當(dāng)參數(shù)等于2的時(shí)候，函數(shù)的返回值是f(1)+2

當(dāng)參數(shù)等于1的時(shí)候，函數(shù)的返回值是f(0)+1

當(dāng)參數(shù)等于0的時(shí)候，函數(shù)的返回值是f(-1)+0

我們發(fā)現(xiàn)，函數(shù)每次都會無條件的調(diào)用自己。

f(x)永遠(yuǎn)不會有具體的值，函數(shù)調(diào)用永遠(yuǎn)不會停止。

要解決這個(gè)問題，我們必須給函數(shù)加入一個(gè)終止條件。

我們再代碼中加入一個(gè)判斷語句：

如果x>0，函數(shù)就調(diào)用自己。

否則，直接返回0。

def f(x) :
    if x>0:
        return f(x-1)+x
    else:
        return 0
print(f(3))

【終端輸出】

6

分析程序執(zhí)行的過程：

【遞推的過程】

f(3)=f(2)+3

f(2)=f(1)+2

f(1)=f(0)+1

f(0)=0

【回歸的過程】

f(0)=0

f(1)=f(0)+1=0+1=1

f(2)=f(1)+2=1+2=3

f(3)=f(2)+3=3+3=6

因此，程序終端輸出的結(jié)果是6。

9.計(jì)算n的階乘

9.1什么是階乘

一個(gè)正整數(shù)的階乘（factorial）是所有小于及等于該數(shù)的正整數(shù)的積。

0的階乘為1。

自然數(shù)n的階乘寫作n!

n!=1×2×3×...×n

階乘可以用遞歸方式定義：0!=1，n!=(n-1)!×n。

【示例】

1!=1

2!=1！×2=1×2=2

3!=2！×3=2×3=6

4!=3！×4=6×4=24

5!=4！×5=24×5=120

9.2計(jì)算5！

def f(n) :
    if n == 1 :
        return 1
    else:
        return n*f(n-1)
print(f(5))

【終端輸出】

120

1. 定義函數(shù)f，參數(shù)是n，注意自定義函數(shù)語句以英文冒號:結(jié)尾；
2. 遞歸函數(shù)的終止條件：如果n=1，返回值為1
3. 自定義函數(shù)要實(shí)現(xiàn)的功能是n*f(n-1)

f(n)和f(n-1)函數(shù)名相同，只是參數(shù)不同。

因此，在自定義函數(shù)f(n)中，它自己調(diào)用了自己。

3. 最后是調(diào)用函數(shù)，調(diào)用函數(shù)的語法為函數(shù)名(參數(shù))

這里的函數(shù)名是f，要傳入的實(shí)際參數(shù)為5。

【參數(shù)傳遞過程】

當(dāng)參數(shù)等于5的時(shí)候，函數(shù)的返回值是5×f(4)

當(dāng)參數(shù)等于4的時(shí)候，函數(shù)的返回值是4×f(3)

當(dāng)參數(shù)等于3的時(shí)候，函數(shù)的返回值是3×f(2)

當(dāng)參數(shù)等于2的時(shí)候，函數(shù)的返回值是2×f(1)

當(dāng)參數(shù)等于1的時(shí)候，函數(shù)的返回值是1，即f(1)=1

【程序的執(zhí)行過程】

【遞推的過程】

f(5)=5×f(4)

f(4)=4×f(3)

f(3)=3×f(2)

f(2)=2×f(1)

f(1)=1

【回歸過程】

f(1)=1

f(2)=2×f(1)=2×1=2

f(3)=3×f(2)=3×2=6

f(4)=4×f(3)=4×6=24

f(5)=5×f(4)=5×24=120

【總結(jié)】

很多同學(xué)會覺得寫代碼比計(jì)算更復(fù)雜，耗費(fèi)時(shí)間更多。

那是因?yàn)槲覀円?jì)算的階乘數(shù)比較簡單。

那如果我們要計(jì)算的是40！，大家觀察下面的代碼的輸出結(jié)果，看看是否還能自己計(jì)算呢？

def f(n) :
    if n == 1 :
        return 1
    else:
        return n*f(n-1)
print(f(40))

【終端輸出】

815915283247897734345611269596115894272000000000