遞迴費氏數列詳解

先列出費氏數列
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)的值，後面依此類推。