iT邦幫忙

7

【python入門教室】(15) 黑魔法,recursion,recursion depon (遞迴函數的介紹)

大家好,我是心原一馬,
其實這標題來自某八○年代卡通的哏。

今天要教一個好用的程式技巧- 遞迴函數
這不光是python的專用語法,
即便你換了一種程式語言,
這邏輯也很好用(但有點燒腦,需在頭腦清晰時撰寫避免混亂)

究竟什麼是遞迴函數?
那麼為什麼小馬稱遞迴函數為黑魔法呢?

https://ithelp.ithome.com.tw/upload/images/20190923/20117114pfb9RIZXt7.png
(圖片來源: 截自動畫「魔法咪路咪路」)

遞迴函數工作原理

遞迴函數就是在一個函數裡面呼叫函數自己稱為遞迴函數,
為什麼要在函數裡呼叫自己呢?
假設我們本來想要解一個比較複雜的大問題但不會解,
但有時若會解一個與原本問題相同類型的小問題,
就可以解開原本的大問題了。

範例一: 階乘

在數學上,n階乘定義為1到n之間所有自然數的乘積,即
n! = 1*2*3*…*(n-1)*n
當然,這個例子很簡單,只需要用for迴圈即很容易計算,
不過我們嘗試用遞迴函數的思想來計算n階乘。

假設我們定義一個函數fact(n),它的效果就是計算n階乘。
那麼如何定義小一點的問題呢?

小一點的問題即是fact(n-1),
假如我們知道小問題fact(n-1)的答案,
我們有沒有辦法推出大問題fact(n)的答案?

答案是肯定的,
因為n! = 1*2*3*…*(n-1)*n = (n-1)! * n
如果可以知道(n-1)階乘是多少的話,
那麼其實只要把(n-1)階乘的答案再乘上n就是n階乘了

所以函數可以簡單定義成這樣:

def fact(n):
    return fact(n-1)*n

感覺就像「黑魔法」一樣吧,
我們只需要把大問題分解成小問題,
便可以透過自己呼叫自己解決這個問題

實際上思考呼叫fact(4)會發生什麼事

fact(4) = fact(3) * 4
        = fact(2) * 3 * 4
        = …

呼叫fact(4)時,根據程式的定義,
會拆開變成fact(3) * 4,
fact(3)又會自動由定義拆解成fact(2) * 3,

但目前這支程式應該會出錯,
還忽略一個重要要素不知讀者們發現了嗎?

遞迴函數兩大要素: 「遞迴關係」與「終止條件」

不知大家是否對遞迴有一點點概念了,
構成遞迴函數的兩大要素便是「遞迴關係」與「終止條件」,

  1. 遞迴關係,也就是本文所稱的「黑魔法」,指函數之間大問題與小問題之間的關係,如上例中的fact(n)=fact(n-1)*n即是一例。
  2. 終止條件,指遞迴關係的停止條件,例如上例的條件應為fact(1)=1

如果沒有終止條件
那麼函數便會無止盡的一直去呼叫自己,
fact(4)去呼叫fact(3)
fact(3)去呼叫fact(2)
fact(2)去呼叫fact(1)
fact(1)去呼叫fact(0)
fact(0)又去呼叫fact(-1)

如此一來沒完沒了,沒有結束的一天

因此,計算n階乘的正確程式為:

def fact(n):
    return 1 if n==1 else n*fact(n-1)

這樣一樣,程式計算fact(4)時,便會在呼叫fact(1)時停下來了:

fact(4) = fact(3) * 4
        = fact(2) * 3 * 4
        = fact(1) * 2 * 3 * 4
        = 1 * 2 * 3 * 4

範例二: 河內塔

河內塔問題是遞迴函數中一個非常經典的例子,
問題為有A, B, C三個石柱,
其中A石柱有n個由大小不一的圓形金片,
由大至小的依序疊在A石柱上,如圖所示:
https://ithelp.ithome.com.tw/upload/images/20190923/20117114axn6JWsQVv.png

規定一次只能移動一個金片到另一個石柱上,
而且小的金片永遠在大的金片上面
那麼請問我們如何將所有金片移動到C石柱上呢?

首先假設我們會解小一點的問題,
即我們知道該如何搬動n-1個金片到另一個石柱上,
那麼整個問題其實可以拆解成三個步驟:

  1. 將A石柱的前n-1個金片搬到B石柱上
  2. 將A石柱最大的金片搬到C石柱上
  3. 將B石柱的n-1個金片搬到C石柱上

最後,別忘了設置終止條件,
當n=1時,直接把A石柱的金片搬到C石柱上即可。
我們假設金片由小到大編號為1,2,…,n,
我們實際實作函數演示要如何搬金片可以達到目的,
程式如下:

def hanoi(n,a,b,c): #將石柱a的n個圓盤移到石柱c(b為輔助)
    if n==1:
        print(f"將1號金片由{a}石柱移動到{c}石柱")
    else:
        hanoi(n-1,a,c,b)
        print(f"將{n}號金片由{a}石柱移動到{c}石柱")
        hanoi(n-1,b,a,c)
        
hanoi(4,'A','B','C')

結果為:

將1號金片由A石柱移動到B石柱
將2號金片由A石柱移動到C石柱
將1號金片由B石柱移動到C石柱
將3號金片由A石柱移動到B石柱
將1號金片由C石柱移動到A石柱
將2號金片由C石柱移動到B石柱
將1號金片由A石柱移動到B石柱
將4號金片由A石柱移動到C石柱
將1號金片由B石柱移動到C石柱
將2號金片由B石柱移動到A石柱
將1號金片由C石柱移動到A石柱
將3號金片由B石柱移動到C石柱
將1號金片由A石柱移動到B石柱
將2號金片由A石柱移動到C石柱
將1號金片由B石柱移動到C石柱

這樣一來,程式就能夠將如何搬金片的過程印出來了,
而我們僅僅是找到大問題與小問題之間的關係,
中間複雜的過程便由程式自行去展開,
神奇不神奇呢?

課後練習

小明在看完心原一馬教遞迴函數的觀念後,
想用遞迴函數的概念撰寫正整數平方和的函數,
即定義f(n) = 1^2+2^2+…+n^2 (這邊^代表次方的意思)

小明發現,如果知道f(n-1)的答案,
f(n) 可以這樣計算 f(n) = f(n-1) + pow(n, 2)
因此小明寫了這個python函數:

def f(n):
    return f(n-1) + pow(n, 2)

然而,小明忽略了一個重點,
使得這個函數無法正確的停下來,
你能幫他修正嗎?
規定修正後的函數裡面不能超過一行程式碼

(對了,假設使用者用這個函數時,會乖乖輸入一個正整數,
不會故意呼叫f(-1)讓你的程式出錯,
你可以不必考慮n<=0的情況)

溫故知新題:
你有沒有辦法不用遞迴函數算出1^2+2^2+…+n^2的值?


1 則留言

4
ccutmis
iT邦高手 4 級 ‧ 2020-04-16 13:04:58

你有沒有辦法不用遞迴函數算出1^2+2^2+…+n^2的值?

是這個嗎...?
https://zhidao.baidu.com/question/92050354.html

心原一馬 iT邦研究生 5 級 ‧ 2020-04-16 14:49:33 檢舉

用數學公式也可 ^^
問一下,你是怎麼插入gif圖檔的啊?
印象中iT邦只能上傳jpg檔與png圖檔耶?

ccutmis iT邦高手 4 級 ‧ 2020-04-16 14:52:04 檢舉

我是用外部圖片連結.../images/emoticon/emoticon82.gif

格式 ![](這裡打圖片網址)
心原一馬 iT邦研究生 5 級 ‧ 2020-04-16 15:31:36 檢舉

好的,謝謝你~

我要留言

立即登入留言