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

1.遞歸的形象解釋

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

視頻作者：pipi的奇思妙想

大家可以網上搜一下該作者的視頻，搜不到的可以聯系我！

【目標任務】

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

2.定義

一個函數是可以調用另一函數的。

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

【示例】

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

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

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

3.步驟

遞歸通常可以分為兩步：先遞后回歸。

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

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

4.終止條件

遞歸函數必須有終止條件。

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

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

當函數運行結束時數據會從棧里取出。

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

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

棧溢出，程序會被操作系統強行終止。

因此，遞歸函數必須有終止條件。

5.優點

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

6.缺點

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

7.調用深度

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

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

8.課堂實例

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

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

【代碼解析】

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

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

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

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

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

【參數傳遞過程】

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

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

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

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

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

我們發現，函數每次都會無條件的調用自己。

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

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

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

如果x>0，函數就調用自己。

否則，直接返回0。

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

【終端輸出】

6

分析程序執行的過程：

【遞推的過程】

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什么是階乘

一個正整數的階乘（factorial）是所有小于及等于該數的正整數的積。

0的階乘為1。

自然數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. 定義函數f，參數是n，注意自定義函數語句以英文冒號:結尾；
2. 遞歸函數的終止條件：如果n=1，返回值為1
3. 自定義函數要實現的功能是n*f(n-1)

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

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

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

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

【參數傳遞過程】

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

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

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

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

當參數等于1的時候，函數的返回值是1，即f(1)=1

【程序的執行過程】

【遞推的過程】

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

【總結】

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

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

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

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

【終端輸出】

815915283247897734345611269596115894272000000000