遞迴 費氏數列詳解


Posted by david-christian on 2023-06-17

先列出費氏數列
0, 1, 1, 2, 3, 5, 8, 13

index 從 0 開始
除了 index 0 與 index 1 以外,該數為前兩個數的總和
例如 index 2 的 1 等於 index 1 的 1 加上 index 0 的 0,依此類推
所以該數的值,與前面的值息息相關
可以得出一個規則,假設 index 是 n,n = (n - 2) + (n - 1)
如果要求出費氏數列 index 6 的位置,也就是 8,遞迴的解法就是先求出前面的 index
當計算到 index 0, 1 時,回傳的值,再回來求出答案

func fibonacci (index int) {
    if index == 0 {
        return 0
    }
    if index == 1 {
        return 1
    }
    return fibonacci(index - 2) + fibonacci(index - 1) 
}

fmt.Print(fibonacci(6)) // 8


fib 是 fibonacci 的 簡寫,透過這張圖,我們可以更瞭解
當我們要求出費氏數列 index 6 的位置
fib(6) = fib(6 - 2) + fib(6 - 1),也就是 fib(4) 跟 fib(5),那要知道 fib(4) 的值,我們就要知道 fib(4 - 2) + fib(4 - 1),此時就是正在遞迴,fib(5) 也是依此類推,這就是前面所說的先求出 index
當 fib(0) 與 fib(1) 的時候,函式就會開始回傳值 0 或 1,當知道 fib(0) 與 fib(1) 的值時,就會知道 fib(2)的值,後面依此類推。

其實遞迴解費氏數列的效能並不好


依據上圖,其實很明顯可以看到,時間複雜度是 bigO 2的n次方
當底數越大時,階層就會越大。










Related Posts

注意! 注意 ! Attention 注意力機制

注意! 注意 ! Attention 注意力機制

基礎格線觀念 筆記

基礎格線觀念 筆記

The way open PDF in android.

The way open PDF in android.


Comments