費氏數列
最近在學寫程式 剛好遇到費氏數列的問題 覺得很有趣 就記錄下來 費氏數列的定義應該不用多說 $$F_0 = 0, F_1 = 1$$ $$ F_n = F_{n-1} + F_{n-2} $$ 那扣要怎麼寫呢 最直觀當然就是照著定義寫遞迴了 def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) 但是這樣數字一大就會很慢 為什麼呢？ 因為很多數字都重複算了 例如算 fib(6) 的時候 由下圖可以看到 f(4) 被算了兩次 f(3) 被算了三次 解決辦法就是把算的結果記起來 就不用再算一次了 可以這樣寫 from functools import cache @cache def fib(n): if n == 0: return 0 if n == 1: return 1 return fib(n-1) + fib(n-2) 不過這樣浪費記憶體空間...