递归算法是每个程序员都知道的算法，函数的递归调用将程序书写变的艺术又简单。对于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) 相同。

小技巧就介绍到这里，祝大家每天收获多多，开心进步！