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

1.遞歸的形象解釋

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

視頻作者：pipi的奇思妙想

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

【目標任務】

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

2.定義

一個函數(shù)是可以調用另一函數(shù)的。

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

【示例】

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

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

像這樣自己調用自己的表達式就是一個遞歸函數(shù)。

3.步驟

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

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

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

4.終止條件

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

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

調用函數(shù)時，程序會將相關的數(shù)據(jù)存儲到計算機的棧里。

當函數(shù)運行結束時數(shù)據(jù)會從棧里取出。

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

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

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

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

5.優(yōu)點

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

6.缺點

遞歸函數(shù)每調用一次都會開相應的內存空間，因此遞歸函數(shù)的缺點就是占用內存較多。

7.調用深度

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

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

8.課堂實例

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

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

【代碼解析】

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

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

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

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

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

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

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

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

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

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

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

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

f(x)永遠不會有具體的值，函數(shù)調用永遠不會停止。

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

我們再代碼中加入一個判斷語句：

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

否則，直接返回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

因此，程序終端輸出的結果是6。

9.計算n的階乘

9.1什么是階乘

一個正整數(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計算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ù)語句以英文冒號:結尾；
2. 遞歸函數(shù)的終止條件：如果n=1，返回值為1
3. 自定義函數(shù)要實現(xiàn)的功能是n*f(n-1)

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

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

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

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

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

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

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

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

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

當參數(shù)等于1的時候，函數(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

【總結】

很多同學會覺得寫代碼比計算更復雜，耗費時間更多。

那是因為我們要計算的階乘數(shù)比較簡單。

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

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

【終端輸出】

815915283247897734345611269596115894272000000000