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 不熟而且也沒寫過費式數列,把學習過程寫成一篇文章印象會更深刻。