iT邦幫忙

2021 iThome 鐵人賽

DAY 9
0
自我挑戰組

30天不怕演算法:白話文版系列 第 9

Day 09:遞迴(2)

上一回我們看到,同樣的跨年倒數任務,可以用迴圈或遞迴的方式完成。

用迴圈通常可以看到某個變數(例如i)記錄著重複執行的次數,可是遞迴的寫法往往更簡潔,好像我們只是丟給它問題,它就幫我們執行下去。讓人不禁好奇簡單背後發生了什麼事。

遞迴的運作

想要更清楚遞迴的運作,我們可以先了解堆疊(stack)這種資料結構。

堆疊是一種線性資料結構,也就是一種連續、有序的資料集合。它的名字就點出它跟現實生活中物體的堆疊一樣,譬如一個廚房裡有人負責洗盤子,他會將洗好的盤子不斷往上疊,另一邊廚師要拿盤子的時候,也會從最上層拿最後放上去的盤子,不可能從底下抽出第一個盤子。

同理,在堆疊中,加入(push)或移除(pop)元素也只會發生在同一端(通常稱為堆疊的頂端,跟堆盤子的意象一樣),而因為後加入的元素會先被移除,堆疊也可以稱作是一種後進先出(LIFO, Last In First Out)的資料結構。

執行堆疊

講到堆疊是因為每當我們執行函式,堆疊這種結構就會被用來儲存函式的資訊。而當進行遞迴時,每次呼叫函式的資訊就被一層層加到堆疊頂上,最後被呼叫的函式會先執行完、從堆疊移除,最後才回到第一個呼叫的函式。

以上一回跨年倒數的例子來說,我們可以想像成當呼叫countDown(n),電腦裡有一個記憶體空間會被用來儲存函式裡的區域變數n。而當執行過程中又呼叫了一次countDown(n-1),就會開始執行這個函式,並把它的資訊加到堆疊上面。

當然,執行堆疊也不是只用來儲存區域變數,更重要的還有儲存返回位址、傳遞變數等功能。例如當函式A中呼叫了子函式B時,主函式A會在堆疊上紀錄返回位址,這樣函式B執行完畢後,就可以把返回位址從堆疊上移除,並回到該位址繼續執行主函式A。

執行堆疊的細節通常藏在我們看不到的後台,不過我們在撰寫遞迴函式時,可以省去一些工作或步驟,就是因為每次呼叫函式都有執行堆疊來記錄其中的值。

遞迴 vs. 迴圈

遞迴跟迴圈除了寫法還有什麼差別?遞迴效能比較高嗎?

遞迴和迴圈主要的差別在於,對於不能預先知道執行次數的問題,可以使用遞迴的解法。迴圈則通常在撰寫時就要先設定程式要重複幾遍。

在效能方面,遞迴其實沒有特別優勢,往往效能還比迴圈差。而且基於上面提到執行堆疊的特性,可以想像當有過多層的遞迴(或不小心無限遞迴)的時候,會出現佔用太多記憶體的問題。

那遞迴和迴圈該怎麼選?

Grokking Algorithms書中提到,Leigh Caldwell在stack overflow網站(對,查資料常用的程式問答網站的名字就是堆疊太多記憶體爆掉的意思)上提供了蠻有趣的回答,不妨可以作為參考,他說迴圈可以增進程式的效能,而遞迴可以增進工程師的效能,應該視情況做出取捨。

也就是說,如果某個地方使用遞迴,能讓程式變得對工程師來說更簡單、直覺、好懂,那就是適合使用遞迴的情況。


上一篇
Day 08:分治法與遞迴(1)
下一篇
Day 10:快速排序(quicksort)
系列文
30天不怕演算法:白話文版30

尚未有邦友留言

立即登入留言