最近在學寫程式
剛好遇到費氏數列的問題 覺得很有趣 就記錄下來
費氏數列的定義應該不用多說
$$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)
不過這樣浪費記憶體空間
要解決的話可以寫迴圈版的
def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
真是太神奇了 傑克
又長姿勢了呢
Ref
Recursive Fibonnaci Method Explained | by Bennie van der Merwe | Launch School | Medium