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

用迴圈通常可以看到某個變數(例如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網站(對，查資料常用的程式問答網站的名字就是堆疊太多記憶體爆掉的意思)上提供了蠻有趣的回答，不妨可以作為參考，他說迴圈可以增進程式的效能，而遞迴可以增進工程師的效能，應該視情況做出取捨。

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