我猜你的直覺反應可能是寫一個像這樣的函數(我也這樣)

然後就吃 TLE 了
也許你會開始懷疑人生，難道遞迴的效率真的那麼糟糕????

遞迴確實會稍微影響效率，但沒有影響那麼誇張，主要問題出在這個寫法有很多重複而冗於的計算

如果我們今天要計算 fib(6) 的值，函數會這樣展開:

仔細觀察可以注意到有一些過程被重複計算了，例如:

fib(6) 中，為了求出 fib(5) ，需要計算 fib(1) 到 fib(4) 的值
為了求出 fib(4) ，需要計算 fib(1) 到 fib(3) 的值
fib(3) 被重複計算了 2 次!!

現在想像一下如果要求 fib(10) 甚至更大的數字時，fib(3) 會被重複計算多少次
而且還不只fib(3)會被重複計算，還有 fib(4)、fib(5)、fib(6) 等著被重複計算

時間複雜度是 O(n^2)

這就是效率差的原因

為了不重覆計算已經做過的結果，需要把已經做過的答案記錄起來，這個動作叫 記憶化Memoization

這邊我用 dict 保存第 n 項的內容(你要用 list 也可以)，建立一個參數 temp 用來紀錄結果，預設為 None
(寫 Python 盡量不使用可變參數做為參數預設值是好習慣，曾搞垮一家大公司，想理解原因看這篇)

初次調用函數時，如果發現 temp 是 None，就建立一份新的
之後每次遞迴都只需要檢查答案有沒有被記錄過，如果沒有就記錄起來，如果有就直接 return

直到算出目標值時再把答案 return 出來

時間複雜度 O(n)

效率不會輸迴圈解

參考資料:
[One Punch 一拳搞定前後端面試] DAY-12 - 記憶化 | iT 邦幫忙 (不過他是用 java 寫的)

剛剛學了新東西

作法是導入 functools 的 lru_cache，然後把它當裝飾器 decorator 用

效果是暫存函數傳入參數與對應的返回值，如果同樣的傳參再次出現，就會直接返回結果，不再計算

需要傳入 maxsize 標記最多記憶多少內容，預設是 128 個，設定成 None 代表無上限

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
   if n == 1:
       return 0
   if n == 2:
       return 1
    return fib(n - 1) + fib(n - 2)

print(fib(int(input())))

其實用的也是和一樓一樣的技術(記憶化)

但整體看上去更簡潔了

還有另一個性質差不多，但不能在 zerojudge 上使用的作法，因為目前這裡用的是 python 3.6 ，而這東西是在 python 3.9 以後才被引入

導入 functools 的 cache

from functools import cache

@cache
def fib(n: int) -> int:
    if n == 1:
        return 0
    if n == 2:
        return 1
    return fib(n - 1) + fib(n - 2)

print(fib(int(input())))

作法幾乎一樣，但不需要主動設定 maxsize，預設是無上限