堆疊的應用: 遞迴

堆疊有一個很重要的應用: 在程式語言中實現了遞迴。

那麼甚麼是遞迴呢?

當妳往鏡子前面一站，鏡子裡面就有一個你的成像。

但你試過兩面鏡子對著一起照嗎?

如果 A、B 兩面鏡子相互面對面放著，你往中間一站，兩面鏡子裡都有你的千百個化身。

為什麼會有這麼奇妙的現象呢?

原來，A 鏡子裡面有 B 鏡子的成像，B 鏡子裡面也有 A 鏡子的成像，這樣反反覆覆就會產生一連串的像中像。

這就是一種遞迴現象。

我們來看看一個精典的遞迴實例: 費氏數列 (Fibonacci)。

為了說明這個數列，這位大佬還舉了一個很具體的例子。

假如兔子在出生兩個月後就有繁殖能力，一對兔子在每個月能生出一對小兔子，假設所有的兔子都不會死，那麼一年以後可以繁殖多少對兔子呢?

我們拿薪出生的一對小兔子分析一下:

• 第一個月小兔子沒有繁殖能力，所以還是一對
• 兩個月後，生下一對小兔子數共有兩對
• 三個月後，老兔子又生下一對，因為小兔子還沒有繁殖能力，所以一共是三對。

所經過月數: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12
兔子對數:   1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144

由此可知這個數列有個明顯的特點: 前面相鄰兩項之和，組成了後一項。

換句話說，遞迴就像是兩面鏡子互照產生無窮影像的「像中像」，而著名的費氏數列就是透過前面兩項相加來決定後一項的經典例子。

今日的分享就到這囉，我們明天見，掰掰！