遞歸算法是每個程式員都知道的算法，函數的遞歸調用将程式書寫變的藝術又簡單。對于c++來說，遞歸算法也是模闆元程式設計中實作循環的唯一方法，為了支援遞歸，c++标準對模闆函數特化點的位置進行了相關規定（...此處離題省略一千字），對對今天說的是python，優雅簡單自帶模闆的python，那麼遞歸一樣發揮了很大的作用，舉例來說，用遞歸實作求一個裴多拉契數列第n項的helloWorld函數，上代碼：
函數1：求裴多拉契數列第n項
仔細一想，計算過程中存在算力浪費，比如求Fibonacci（100）需要遞歸計算Fibonacci（99）和Fibonacci（98），在計算Fibonacci（99）和Fibonacci（98）時都重新計算了Fibonacci（97）。這種浪費可能會造成運作時間數量級增長，這也是在遞歸算法中經常遇到的問題。
而動态規劃算法往往可以杜絕此類浪費，通俗的說，動态規劃就是邊存邊算，充分利用之前結果，例如函數1用動态規劃思路可以寫成：
函數2：求裴多拉契數列第n項(動态規劃)
動态規劃版的函數2使用字典把每項值存下來，沒有重新計算的浪費。動态規劃雖然也是經典的好思路，但對于某些問題沒有遞歸那麼直覺。有沒有辦法直接讓函數1擁有函數2的計算效率呢？今天介紹的python自帶神器就可以做到，即functools.lru_cache裝飾器。函數加上這個裝飾器，就可以把計算過的結果存儲在全局字典裡，如果再次調用相同參數，則直接從全局字典擷取，無需再次計算。lru是Least Recently Used政策，即隻存儲最近使用的幾個值，存儲數量由maxsize參數指定，如果該參數設為None，則該政策被禁用，存儲容量無限。上代碼：
函數3：使用裝飾器的遞歸函數
函數3隻增加了一行，其效率已經和函數2等同（如果在代碼中函數需要多次運作還會勝出，因為函數2把值存在局部變量裡，每次運作要重新計算），而且完全是遞歸的寫法。筆者在leecode做題時加了一行裝飾器，把一道逾時遞歸解法變成了運作速度超過99%的神解。
此外，python3.9 新增了functools.cache裝飾器，效果與 functools.lru_cache(maxsize=None) 相同。
小技巧就介紹到這裡，祝大家每天收獲多多，開心進步！