要避免因遞迴呼叫浪費函式重複計算的時間，可以使用記憶化技術（Memoization）。記憶化是一種優化技術，用於加速計算機程式中冗餘計算的部分。以下是修改後使用遞迴方式並利用記憶化技術的費氏數列函式程式碼：
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n == 0:
result = 0
elif n == 1:
result = 1
else:
result = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
memo[n] = result
return result
# 測試範例
for i in range(10):
print(f"F({i}) = {fibonacci(i)}")
解釋
使用字典作為記憶表 (Memoization Table)：
在函式中添加一個參數 memo，默認值為 None。memo 用於儲存已經計算過的 F(n) 值。
在首次調用函式時，初始化 memo 為空字典。
查找記憶表：
每次計算 F(n) 時，首先檢查 n 是否在 memo 中。如果是，則直接返回 memo[n]，避免重複計算。
計算和記憶：
如果 n 不在 memo 中，按照費氏數列公式計算 F(n) 的值。
將計算結果儲存在 memo[n] 中，以便後續使用。
基本情況 (Base Cases)：
當 n 等於 0 時，返回 0。
當 n 等於 1 時，返回 1。
這樣的修改使得遞迴計算費氏數列時不會重複計算已經求得的值，大大提高了計算效率。
阿摩線上測驗
登入