面試被問到的題目，雖然是很基本的題目，但相關延伸也有不少，寫篇文章記錄一下。
遞迴：最基本又直觀的解法
def fibonacci(n):
if n < 3:
return 1
return fibonacci(n-1) + fibonacci(n-2)
時間複雜度
$O(2^n)$，每次呼叫 fibonacci(n) 都會進行額外兩次呼叫，n 每次會 -1，直到 n == 2。整個呼叫會是高度 n 的二元樹的子集合，而每次運行時間都是 $O(1)$，因此整體時間的 upper bound 就是二元樹的節點數量：
$$
2^0 + 2^1 + 2^2 + … + 2^{n-1} = \frac{2^n - 1}{2 - 1}
$$
空間複雜度
$O(1)$
遞迴優化：利用 Hash 減少計算次數
在原本的解法中，會有很多次重複計算 fibonacci(n-1), fibonacci(n-2) … 等，因此可以把計算結果儲存起來，
def fibonacci(n):
table = {}
def fib_table(n):
if n < 3:
return 1
table[n] = fib_table(n-1) + fib_table(n-2)
return table[n]
return fib_table(n)
這邊我利用了 Python 變數 scope 的 LEGB 特性，也就是查找順序為：local, enclosed, global, built-in。可以參見官方 document，有趣的是 LEGB 並不是官方名詞而是社群流傳的口訣。
也許聽起來很複雜，但其實也就是簡單的往外查找規則罷了。
因此 table 雖然是在外部的 fibonacci 定義的，但 fib_table 內（local）沒有另外定義 table 變數的情況下，會往外查找，因此可以讀取外部的 table（enclosed）。
可能有人會問，我有 assign 值到 table 內部啊，這樣不用宣告 global table 嗎？答案是不需要的，在 Python 中，table 變數存的是物件的 reference，因此改變物件內的屬性並不會影響 table 這個變數。而 table[n] = fib_table(n-1) + fib_table(n-2) 這行實際上是呼叫了 table 指向的物件的 __setitem__ 方法，改變物件內部的屬性。
時間複雜度
$O(n)$，對每個 n 只需要算一遍，不會每次都要往 n-1，n-2 展開。
空間複雜度
$O(n)$，table 需要存 fib_table(3) 到 fib_table(n) 的結果。
遞迴優化：使用 Cache
Python 有內建的 Cache 可以記錄函式呼叫結果：
@cache
def fibonacci(n):
if n < 3:
return 1
return fibonacci(n-1) + fibonacci(n-2)
這其實就是第一個解法加上一行 @cache 而已。
在函式開頭加上 @something 的寫法是呼叫 Python 中的 decorator，是 Python 中一個重要的特性。在 Python 語言中，函式是一等公民，也就是函式可以被當作變數 assign，也可以當作參數傳遞。 decorator 實際上就是把他裝飾的函式傳到 decorator 內部再做一些事情，以這邊的 @cache 為例，decorator 會自動幫忙把 fibonacci 這個函式的呼叫結果記錄起來，並回傳包裝後的函數，我們最後拿到的 fibonacci 實際上會多了包裝後的方法：
> fibonacci.__dir__()
['cache_parameters',
...
'cache_info',
'cache_clear',
...
]
比自己用 hash 實作簡單多了。
這邊的 cache 實際上是 functools.lru_cache(maxsize=None)，一個不限制大小的 LRU Cache，如果想要限制大小可以在修改 maxsize 發揮 LRU 的功能。
學會了這招才是真正的 Pythonist。
Cache Size 要設定成多少？
既然可以設定 cache size，我們真的需要一直記著每次計算的結果嗎？
當計算第 n 項時，只需要 n-1 和 n-2 兩項結果，所以就設成 2 就好了對吧？但如果直接這樣改，會發現程式跑的時間還是會變很長。
實際上當計算 n-1 時，需要知道 n-2 和 n-3 的值，先計算 n-2 後計算 n-3。因此最後 cache 內記錄的會是 n-1 和 n-3 的值。
所以會在接下來算 n-2 時造成一個 cache miss。
如果不改其他部分，可以把 maxsize 設成 3，就可以避免掉這個 cache miss。
但仔細思考，其實會有這個 miss，歸根究底是我們先計算比較靠近 n 的 n-1，後計算比較遠離 n 的 n-2 造成的。那何不將兩者交換呢？
@lru_cache(maxsize=2)
def fibonacci(n):
if n < 3:
return 1
return fibonacci(n-2) + fibonacci(n-1)
做完簡單的修改，一樣漂亮的 code，可以給出不錯的時間複雜度和常數的空間複雜度。
時間複雜度
$O(n)$，不會有 cache miss，每個 n 只需要計算一次。
空間複雜度
$O(1)$，因為 cache size 最大是 2。
尾遞迴 Tail Recursive / Tail Call
當函式本身在回傳時會呼叫自己即為尾遞迴，可以說是遞迴中的特例。
要撰寫尾遞迴，需要思考每次遞迴時我們往前取了什麼資訊。在上一個 LRU cache 的解法中知道，我們只需要紀錄 n-2 和 n-1 兩個值即可。分別命名為 f1 和 f2，每次呼叫我們把 n 減 1，把 f1 指定為 f2，並把 f2 改為 f1 + f2：
def fibonacci(n):
def fib_tail_recursive(n, f1, f2):
if n < 3:
return f2
return fib_tail_recursive(n - 1, f2, f1 + f2)
return fib_tail_recursive(n, 1, 1)
尾遞迴的版本我認為比較不好理解，但是為了下一個迭代法，還是練習了一下尾遞迴的解法。
下面對於不同的 n 做分析：
- 初始時
f1和f2分別代表第一項和第二項，都是 1。 - 當 n < 3 時直接回傳
f1為 1 - 當 n = 3 時，會跑一次尾遞迴，此時 n 變成 2，
f1變成 1，f2變成 1 + 1 = 2，接著回傳f2即為 2
以下依此類推…
時間複雜度
$O(n)$，從 n 呼叫到 2。
空間複雜度
$O(1)$，沒有額外的 cache 或是查表。
迭代法：使用迴圈，攤平遞迴
尾遞迴是攤平遞迴的中間做法，可以寫成尾遞迴的函式，就能快速改寫成迭代形式：
def fibonacci(n):
f1, f2 = 1, 1
for i in range(2, n): # 當 n < 3 時不會進入迴圈
f1, f2 = f2, f1 + f2
return f2
做的事情和尾遞迴版本一模一樣。
也因此有些語言對於尾遞迴有做優化，當編譯器看到尾遞迴，會自動幫你攤平成迴圈（用 GOTO 實現），稱為尾遞迴優化（Tail Call Optimization）。主要會在以 functional programming 為主的語言中看到，例如 erlang 或是 haskell。
很可惜，Python 是沒有支援的那部分。
時間複雜度
$O(n)$，只有一個迴圈，迴圈內部運算都是 $O(1)$
空間複雜度
$O(1)$，只用了固定兩個變數
其他解法
雖然到這邊已經說明完正常的解法，但其實費氏數列還有更多有趣的解法。
時間複雜度更短的 $O(\lg n)$ 的：