Python中如何优化递归函数以避免栈溢出错误

今天又做了一次 markdown parser 的 benchmark，发现 markdown2 更慢了。原先是循环 1000 次的，发现等了很久都没有跑完，于是改成 loop 100 次了：

Parsing the Markdown Syntax document 100 times...
mistune: 0.844159
misaka: 0.042687
markdown2: 20.962605
markdown: 3.57699099999

最开始写 mistune 时的 benchmark: https://github.com/lepture/mistune/issues/1

当时写的文章： https://lepture.com/en/2014/markdown-parsers-in-python


Python中如何优化递归函数以避免栈溢出错误

11 回复

不懂你们用 Markdown 编辑器的，纯手打。


递归函数在深度过大时确实容易导致栈溢出。核心优化思路有两个：尾递归优化和改用迭代。

Python官方解释器（CPython）没有实现尾递归优化，所以第一个方法基本没用。咱们得用第二个：把递归改成迭代，通常配合栈或队列这种数据结构手动管理状态。

举个例子，算阶乘的递归函数：

def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)

这个在n很大时会爆栈。改成迭代版本：

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

对于更复杂的递归，比如深度优先遍历，可以用一个显式的栈来模拟：

def dfs_iterative(start_node):
    stack = [start_node]
    visited = set()
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            # 处理当前节点
            for neighbor in node.neighbors:
                if neighbor not in visited:
                    stack.append(neighbor)
    return visited

再比如斐波那契数列，递归效率极低，可以改用循环或者配合缓存：

def fib_iterative(n):
    if n < 2:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

总结：别指望Python的尾递归，老实把递归拆成循环加栈。

表示一直在用……

喜欢纯 py 的实现

标题应该改为：

本人测试 markdown2 效率不高，建议高效率需求时不要用

早就已经转到 asciidoc 阵营了
markdown 的表达能力以及兼容性不是很好，
写起来各种第三方扩展语法。。。

asciidoc 感觉更麻烦额

不，markdown2 不仅是速度慢，而且实现上各种问题。而它的说明居然带有 fast，给人一种比 markdown (1) 快的感觉。

怎么说呢，这个 markdown2 的库真的是一无是处，看着有这么多人在用，心疼大家。可能很多人都认为 2 一定比 1 好，但其实完全不是这样。

原来您是 http://mistune.readthedocs.io/en/latest/ 的作者

文中有提到：

> 最开始写 mistune 时的 benchmark

回到顶部