使用 functools.lru_cache 加速 Python 递归函数

江屿

发布时间：2026-10-13| 4人浏览过

原创

本文介绍如何使用 Python 内置的 functools.lru_cache 装饰器优化递归函数的执行效率。通过一个在嵌套结构中查找元素的示例，对比了启用缓存前后的运行时间，展示了 lru_cache 如何避免重复计算并显著提升递归性能。

引言与装饰器简介

本文将介绍一种高效的 Python 技术：[装饰器]。

注记：此处提到的“装饰器”参考 Python3 官方教程中的相关章节。如需快速了解装饰器的基本概念，可查阅该教程。

使用 @functools.lru_cache 装饰器可以对函数执行结果进行缓存（Memoization），从而显著提升递归函数的执行速度。

递归优化示例：查找宝藏

示例场景：在一个嵌套的元组（tuple）或列表（list）结构中查找特定元素 'Gold Coin'。


import time
from functools import lru_cache
def find_treasure(box):
 for item in box:
  if isinstance(item, (tuple, list)):
   find_treasure(item)
  elif item == 'Gold Coin':
   print('Find the treasure!')
   return True
start = time.perf_counter()
find_treasure(('sth', 'sth', 'sth',
    ('Bad Coin', 'normal coin', 'fish', 'sth', 'any sth'),
    ('Bad Coin', 'normal coin', 'fish', 'sth', 'any sth'),
    'Gold Coin', ))
end = time.perf_counter()
run_time_without_cache = end - start
print('在没有Cache的情况下，运行花费了{} s。'.format(run_time_without_cache))
@lru_cache()
def find_treasure_quickly(box):
 for item in box:
  if isinstance(item, (tuple, list)):
   find_treasure(item)
  elif item == 'Gold Coin':
   print('Find the treasure!')
   return True
start = time.perf_counter()
find_treasure_quickly(('sth', 'sth', 'sth',
      ('Bad Coin', 'normal coin', 'fish', 'sth', 'any sth'),
      ('Bad Coin', 'normal coin', 'fish', 'sth', 'any sth'),
      'Gold Coin', ))
end = time.perf_counter()
run_time_with_cache = end - start
print('在有Cache的情况下，运行花费了{} s。'.format(run_time_with_cache))
print('有Cache比没Cache快{} s。'.format(float(run_time_without_cache-run_time_with_cache)))

程序最终输出结果如下：

Find the treasure! 在没有Cache的情况下，运行花费了0.0002182829999810565 s。 Find the treasure! 在有Cache的情况下，运行花费了0.00011638000000857573 s。有Cache比没Cache快0.00010190299997248076 s。

测试环境与性能分析

注记：运行上述示例时，我的电脑硬件配置如下：


CPU:AMD Ryzen 5 2600
RAM:Kingston HyperX 8Gigabytes 2666

该配置已使用约7个月。

该装饰器的作用是在函数运行时记录其输入参数与对应的运行结果。当相同的元组 ('Bad Coin', 'normal coin', 'fish', 'sth', 'any sth') 第二次出现时，添加了该装饰器的函数 find_the_treasure_quickly 不会再次进入递归逻辑进行查找，而是直接从“备忘录”中读取并返回之前的计算结果。