你好，我是 somenzz，Python 的靈活程度讓人發(fā)指，今天來分享一下關(guān)于字典的瘋狂操作，計(jì)算斐波那契數(shù)列，話不多說，先看代碼:

代碼定義了一個(gè)類 FibDict，繼承自 dict，自定義了魔術(shù)方法 __missing__ 當(dāng) dict 查找 key失敗(missing)的時(shí)候，會(huì)由 Python 解釋器自行調(diào)用改方法。換句話說，如果試圖從 dict 中獲取不存在的 key，就會(huì)執(zhí)行這個(gè)方法。

因此計(jì)算 fib_dict[10] 就會(huì)執(zhí)行這個(gè)方法，計(jì)算 fib_dict[9] 和 fib_dict[8]，就這樣遞歸，一直到 fib_dict[0]和 fib_dict[1]。

這是遞歸，但是字典是一種 hash 表，只要計(jì)算過的數(shù)據(jù)不會(huì)重復(fù)計(jì)算，因此效率非常高。

我們可以驗(yàn)證下計(jì)算 fib_dict[200] 的耗時(shí)：

可以看出連 1 毫秒都不到。

不過，遞歸雖爽，可不要貪杯哦，任何事情都有極限，1000 是遞歸的默認(rèn)極限(sys.getrecursionlimit() ==1000)，如果你直接計(jì)算 fib_dict[501] 就拋出 RecursionError 異常。

你可能有個(gè)小小的疑問，為什么遞歸的深度是 1000，但我調(diào)用 501 次就不行了呢?其實(shí)原因在于 __missing__ 調(diào)用了 __setitem__，__setitem__ 又調(diào)用了 __missing__，因此每個(gè)缺失的 key 其實(shí)調(diào)用了兩次，所以超過 500 就會(huì)報(bào)錯(cuò)。

但是，字典是有記憶的，如果你這樣調(diào)用它，永遠(yuǎn)不會(huì)出現(xiàn)遞歸的問題：