如何在Python中优化递归函数？

你们有没有这种经历？就是写个递归的代码，特别优雅特别清晰，然后一跑数据——直接卡死，CPU干到100%，人都傻了。

我印象最深的是去年写那个树结构的那个处理逻辑...我们组的小李就用递归遍历，结果客户数据一多，直接栈溢出了...你知道吧，就是 Python 里那个 RecursionError: maximum recursion depth exceeded，异常都给你整明白了。后来我们一顿折腾，总算是找到一些比较稳的优化方式。

一、尾递归优化？别想了，Python不支持

有人一上来就问，那我们用尾递归优化不就完了？醒醒啊哥，Python 没这个优化！虽然你写得再像尾递归，它照样不会优化。

deftail_rec(n, acc=1):
if n == 0:
return acc
return tail_rec(n - 1, n * acc)

这段代码看着像是尾递归对吧？理论上应该很好优化，可是 Python 不管这些，你递归层数上来了，它该爆栈还是爆栈。所以除非你用 PyPy，否则...别指望这个。

二、最靠谱的：加缓存，memoization走起

我们那个场景就是典型的重复计算，后来我让小李给递归函数加了个 lru_cache，性能直接翻了好几倍。就这玩意：

from functools import lru_cache

@lru_cache(maxsize=None)
deffib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)

你要是不加缓存，fib(35) 就够你等一会了，加了之后嗖一下就出来。其实这方法特别适合纯函数，不改全局状态、没有副作用的那种。

三、递归改循环，土办法但稳

说实话我一开始特别排斥改成循环，总觉得递归优雅些，但真到线上你就知道，管他优不优雅，能活着比什么都强。像我们那个项目里的后代节点查找逻辑，我后来就直接改成了 stack + while：

defdfs_iterative(tree, root_id):
    stack = [root_id]
    visited = []
while stack:
        node = stack.pop()
        visited.append(node)
for child in tree.get(node, []):
            stack.append(child)
return visited

这种写法虽然啰嗦点，但是不怕深度了，也不会爆栈，CPU利用率也好控制。尤其是你还要多线程处理的时候，递归根本没法玩。

四、动态规划+状态压缩，进阶玩法

我有次搞那个路径最短的算法，开始也是递归写的，搞得我又缓存又裁剪的，后来干脆直接 DP+数组滚动，一下就顺了。

defclimb_stairs(n):
if n <= 2:
return n
    a, b = 1, 2
for _ in range(3, n + 1):
        a, b = b, a + b
return b

你看是不是很像 fib 的循环写法，其实本质就一个套路：把原来递归里每一层的中间结果都放下来，用空间换时间。空间压力能接受的话，这招特别香。

五、如果数据大还得加并行

你别说，这种改完之后，CPU还不够用了。去年那个批量图结构分析，我们就直接用 concurrent.futures 搞并行递归（其实不是真递归，是分片 + 并行）：

from concurrent.futures import ThreadPoolExecutor

defprocess_chunk(chunk):
return [fib(n) for n in chunk]

with ThreadPoolExecutor(max_workers=4) as executor:
    results = list(executor.map(process_chunk, chunks))

当然这块不是每个递归都适合，得你函数是独立计算的才行，有依赖关系就麻烦了。

优化递归这事儿啊，真不是改一两个地方能解决的，有时候你得问自己，**这递归真的必要吗？**能不用就不用吧兄弟们。递归写着爽，用着疼啊。

哦对，说了这么多，突然想起来，昨晚我还没洗衣服去...你们先聊，我去扔洗衣机一下。