Use recursion to log a Fibonacci sequence of n length.
利用遞迴來輸出長度為 n 的費波那契數列，即費氏數列
最後更新時間：2023–10–01
前言
其實沒有什麼前言，只是曾在這篇的前言提過（一個前言裡的前言的概念），最近因為要開始面試所以部落格文章不會寫太長免得花太多時間，以小品文為主，主題大多是那種對面試有點益處的，幫助自己複習些基本觀念。這次是在準備面試考古題時發現的有趣題目，標題那句話即為題目本身，也就是費式數列，廢話不多說直接開始吧。
什麼是 recursion？
解題總要先看懂題目吧，這道題大概會是 recursion 跟 Fibonacci 這兩個字看不懂，先來看第一個，recursion 就是遞迴，寫到這邊忍不住去查這個字，依照本部落格風格（尿性？）就很想說文解字一下，明明不想花太多時間但又很想去查XD
對這個字不熟，稍微比較常遇到就是在學程式之後，一開始看到以為跟什麼詛咒（curse）有關，去查才知道是遞迴，但遞迴也不好解釋，所以想說 re 開頭代表重複 XX 東西，那查查看 cursion 吧，結果發現沒這個字，於是去查字根看到一個比較接近的，curr 或 curs 會跟 run 有關，所以像 excursion 是遠足或離題、incursion 為入侵或流入，大概可以抓到一點點感覺，cursion 或許跟行走、前進有關，因此 recursion 大約是重複地走過那種感覺。
啊所以遞迴是啥？先來看看維基說明：
遞迴（英語：Recursion），又譯為遞歸，在數學與電腦科學中，是指在函數的定義中使用函數自身的方法。遞迴一詞還較常用於描述以自相似方法重複事物的過程。
以白話來說就是某個東西重複它自己，以程式而言就是某個函式內又呼叫了自己，於是就會一直重複執行函式本身。
想到一個生活情境很適合當作遞迴的例子，就是當使用一些軟體如 Discord 分享自己螢幕畫面時，會在畫面中看到自己分享的畫面，而畫面若剛好就停在 Discord，那就會在分享畫面中看到自己分享的畫面（也就是 Discord），而在該分享畫面中又會看到該分享畫面裡的分享畫面，以此生生不息，就像這樣：
既然有點概念了，那就用程式來寫寫看吧，一樣用我最常用的水果來說明，猜猜看 console 會印出什麼？
function buyFruit(n) {
if(n===0) return console.log("Finish!")
console.log(`I wanna buy ${n} apples.`)
return buyFruit(n-1)
}
buyFruit(3)答案是：
I wanna buy 3 apples.
I wanna buy 2 apples.
I wanna buy 1 apples.
Finish!來看一下註解版：
function buyFruit(n) {
// 先給定一個停止條件，如果數量變成 0 那就結束，不會再回傳函式本身
// 可以試試看沒寫這行會發生什麼事，嘗試前建議把其他重要分頁先存檔XD
if(n===0) return console.log("Finish!")
// 輸出：我想買 n 顆蘋果
console.log(`I wanna buy ${n} apples.`)
// 回傳函式本身，此時讓 n - 1，所以如果一開始是買 3 顆，就會回傳一個買 2 顆的函式
// 而買 2 顆的函式印出買 2 顆蘋果後，會再回傳買 1 顆的函式，以此類推，直到 n 為 0
return buyFruit(n-1)
}
// 執行函式，買水果囉
buyFruit(3)這樣應該對遞迴有點瞭解了吧，不過老實說自己寫程式很少用到 recursion，可能現在還太淺。
什麼是費氏數列？
Fibonacci 這個字一看就很義大利，先幫你附上維基，反正就是某位義大利數學家在其著作提出的，不過這種數列最一開始應該不是他發現或創造，源頭或許不可考，但費大哥有可能是第一位寫進書裡的，但不管怎樣反正最有名，這種數列也以他命名。費氏數列由 0 和 1 開始，之後的費波那契數就是由前兩個數字相加，例如：
0、1、 1、 2、 3、 5、 8、 13、 21、 34
很像智力或邏輯測驗會出現的數列。這個東西滿神奇的，大自然中可以發現不少費氏數列，例如樹的分枝數量、葉子在枝條上的排列、鳳梨身上鱗片排列、松果鱗片排列、花瓣數量等等，以上都是某些品種的植物會出現，並非所有種類都有，有興趣可以看看這個影片：大自然的數學密碼：Fibonacci Numbers，不禁覺得：大自然真奇妙，就看你有沒有注意到～（絕對不會承認自己聽過這首歌）
解法
所以要怎麼寫呢？以下都是用 JavaScript 來寫：
function fibonacci(n) {
if (n === 0) return 0;
if (n === 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}
function logFibonacciSequence(length) {
for (let i = 0; i < length; i++) {
console.log(fibonacci(i));
}
}
logFibonacciSequence(10)如果想自己思考的這邊先防雷，若想繼續往下再來看說明。
好了嗎？
Let’s go
解法說明
不囉嗦來看註解版：
function fibonacci(n) {
// 這兩行其實就是停止條件，也是所有數字計算的基礎，都是從這往上加的
if (n === 0) return 0;
if (n === 1) return 1;
// 決定要回傳的東西，也就是回傳該數字的前兩位數字相加
// 例如第 5 個就是回傳第 4 個 + 第 3 個
// 而第 4 個會進一步回傳第 3 個 + 第 2 個；而第 3 個則回傳第 2 個 + 第 1 個
// 以此類推
return fibonacci(n - 1) + fibonacci(n - 2);
}
// 把每個數字印出來，看要印幾個，因為題目是要整個數列而非第幾個數字
function logFibonacciSequence(length) {
for (let i = 0; i < length; i++) {
console.log(fibonacci(i));
}
}
// 輸出長度為 10 的費氏數列，也就是共有 10 個數字
logFibonacciSequence(10)如果覺得不好懂的話，可以自己加上 console.log 把執行過程印出來，例如：
function fibonacci(n) {
console.log(`現在是第 ${n} 個數字`)
if (n === 0) return 0;
if (n === 1) return 1;
console.log(`即將回傳 ${n-1} 的函式`)
console.log(`即將回傳 ${n-2} 的函式`)
return fibonacci(n - 1) + fibonacci(n - 2);
}
function logFibonacciSequence(length) {
for (let i = 0; i < length; i++) {
console.log(fibonacci(i));
}
}
logFibonacciSequence(5)會印出以下內容（我在每個數字被印出前的某些行另外加上註解方便說明）：
現在是第 0 個數字 // 直接回傳 0
0
現在是第 1 個數字 // 直接回傳 1
1
現在是第 2 個數字
即將回傳 1 的函式
即將回傳 0 的函式
現在是第 1 個數字 // 直接回傳 1
現在是第 0 個數字 // 直接回傳 0，所以 1 + 0 為 1
1
現在是第 3 個數字
即將回傳 2 的函式
即將回傳 1 的函式
現在是第 2 個數字
即將回傳 1 的函式
即將回傳 0 的函式
現在是第 1 個數字 // 回傳 1
現在是第 0 個數字 // 回傳 0
// 最後回傳 1，所以 1 + 0 + 1 為 2，也就是第 2 個數字（1 + 0） + 第 1 個數字（1）
現在是第 1 個數字 // 回傳 1
2
現在是第 4 個數字
即將回傳 3 的函式
即將回傳 2 的函式
現在是第 3 個數字
即將回傳 2 的函式
即將回傳 1 的函式
現在是第 2 個數字
即將回傳 1 的函式
即將回傳 0 的函式
現在是第 1 個數字 // 回傳 1
現在是第 0 個數字 // 回傳 0
現在是第 1 個數字 // 回傳 1
現在是第 2 個數字
即將回傳 1 的函式
即將回傳 0 的函式
現在是第 1 個數字 // 回傳 1
// 最後回傳 0，所以總共是 1 + 0 + 1 + 1 + 0 為 3
// 也就是第 3 個數字（1 + 0 + 1） + 第 2 個數字（1 + 0）
現在是第 0 個數字 // 回傳 0
3這樣應該就滿清楚了。這邊注意一下，可能要看題目有沒有說從 0 或 1 開始，第 0 項（也就是第 1 個數字）會不一樣。
結尾
結果好像不小心又寫得比自己預設篇幅長，如果本篇對你有幫助那就太棒了，但其實寫這篇最想幫的人是我自己XD，對 recursion 不熟而且也沒寫過費式數列，把學習過程寫成一篇文章印象會更深刻。
