6.？無尾遞歸的實用方案
如前所述，斐波那契數列典型遞歸解法的時間復雜度為O (1.618 N)，呈指數增長，沒有實用價值。
仔細看遞歸調用過程，會發現calculate _ Fibonacci _ sequence(n-1)+calculate _ Fibonacci _ sequence(n-2)的二進制遞歸過程會有很多重復的中間結果。
然後在遞歸過程中，將中間結果保存在壹個字典中，在字典中檢查每壹次遞歸調用，看是否是參數相同的調用，如果是，則直接返回保存在字典中的值。
這樣，算法的時間復雜度降低到O(n)。通過緩存技術，時間復雜度被降低到可用的水平。
開始編寫這個遞歸緩存裝飾器。Python中廣泛使用了Decorators，在很多情況下便於模塊化級聯。
我們來試試效果，算物品100。
原來卡住的情況沒了，結果秒出。
好的，再來計算壹下1200項。
堆棧溢出錯誤
也是實用性的障礙。Python默認的堆棧空間不大，只有1000。Python官方不推薦遞歸，盡量寫成叠代循環。而官方的思路是默認設置壹個小的堆棧空間。如果程序有太深的遞歸，可以在運行時早期暴露和重寫。
但是有時候遞歸的寫法確實簡潔明了，在對效率沒有要求的時候還是可以用的。
那麽解決遞歸過程中溢出誤差的壹種方法是動態增加設定的極限值。
您可能認為使用decorator是實現它的壹種優雅方式。
但是，當考慮到遞歸函數運行後要恢復recursionlimit的初始值時。
Decorator不可能簡單的壹個人完成這個目標(如果妳有什麽好的想法，請在下面留言討論_)
我通過傳入函數參數來實現這個解決方案。
我們來試試效果。
運行時間與前面的示例相同，總時間為0.012642秒。
問題解決
讓沒有實用價值的斐波那契數列的遞歸解成為可用的遞歸解。
未完待續。
斐波那契數列的高效求解及時間復雜度分析之四