递归应用于 Python 中的列表与树

Question

我对递归的主要关注是Python中的递归限制，我认为是1000。考虑到这一点，我想讨论两种情况：

场景 1：对平衡树（二叉树）应用递归

例如，要搜索树中的最大值：

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max(root):
    max_left = max(root.left)
    max_right = max(root.right)
    if max_left > root.value and max_left > max_right:
        return max_left
    if max_right > root.value and max_right > max_left:
        return max_right
    else:
        return root.value

这里，在任何给定时间堆栈中的最大调用次数将是树的高度，即 log_2(n)，其中 n 是列表中元素的数量。鉴于 Python 中的限制是 1000 次调用，树可以存储多达 2^1000（或 2^999）个元素而不会达到调用限制。对我来说，这不是真正的限制，所以我假设我们可以在这里使用递归。

场景 2：对列表应用递归

一个虚拟示例将计算列表的最大值，因此我们 return 列表头部与列表其余部分相同函数的结果之间的最大值：

def max(l):
    if len(l) == 1:
        return l[0]
    max_tail = max(l[1:])
    if l[0] > max_tail:
        return l[0]
    else:
        return max_tail

输出：

>>> max(list(range(998)))
997
>>> max(list(range(999)))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 4, in max
  File "<stdin>", line 4, in max
  File "<stdin>", line 4, in max
  [Previous line repeated 995 more times]
  File "<stdin>", line 2, in max
RecursionError: maximum recursion depth exceeded while calling a Python object

所以我的理解是，对于列表，递归不是一个合理的选择，因为它通常不能处理大于 999（甚至更少，取决于堆栈跟踪）的列表。

现在，我的问题：

使用递归处理平衡树是否合理？
对于大多数问题（列表、非平衡树等）来说，这是真的吗？
这里还有什么我应该考虑的吗？我只是想了解更多关于在使用 Python.

Answer 1

如果您真的想以递归方式编写代码，您可以在 Python 中进行蹦床操作。但是迭代地编写代码要现实得多。

您可以创建基于生成器的蹦床函数，如此博客中所示 post：

http://www.usrsb.in/blog/blog/2012/08/12/bouncing-pythons-generators-with-a-trampoline/

def tramp(gen, *args, **kwargs):
    g = gen(*args, **kwargs)
    while isinstance(g, types.GeneratorType):
        g=g.next()
    return g

也可以在Python中更改递归限制，不总是推荐，也很少能称为合适的解决方案；但这是可能的。

from sys import setrecursionlimit
setrecursionlimit(10**8)

Answer 2

首先，请记住，语言与语言的实现不同。 Python 中的调用堆栈大小因实现而异。 1000 的限制适用于 CPython 但不一定适用于所有实现。

Is it reasonable to use recursion to process balanced trees?

递归对于平衡树是合理的。正如您已经非常清楚地描述的那样，最大调用堆栈深度是结构大小的对数因子。你需要大量的输入才能炸毁堆栈。

对于列表或退化的不平衡树，递归是不合适的，因为最大调用堆栈深度在结构长度上是线性的。

也就是说，我认为在 Python 中没有必要经常使用自平衡树。大多数工作是在列表和字典上完成的，偶尔会嵌套和递归定义。递归恰好适合树之类的结构这一事实并不意味着它通常广泛适用于 Python.

Is it true that for most problems it is just not an option (lists, non-balanced trees, etc)?

是的，但是 CPython 中的设计禁止递归。 Python 是 not a functional language. CPython doesn't support tail call optimization and "never" will.

Guido 有一个很棒的 blog post 捍卫了 CPython 的反递归设计。不管你是否同意这种设计，工具通常应该按预期使用，而不是人们希望的那样。

在紧要关头，Python（作为一种多范式语言）可以支持以函数式风格编写的代码，并且有，但这并没有改变它们的事实重新解决方法。

Anything else that I should take into account here? I am just trying to learn more about when recursion is the good option in general when using Python.

CPython 中的函数调用比迭代有更多的开销（时间和 space），因此即使结构大小适合调用堆栈或您使用支持深度递归的技巧。

Using setrecursionlimit is unsafe and almost never necessary。大多数语言都没有这样的选项。增加它意味着你有运行操作系统杀死 CPython 解释器的风险。当然，摆弄限制对于快速脚本和调试会派上用场，但这不是通用的解决方案。

recursion tag is flooded with questions from well-meaning CS students tasked with solving problems with recursion similar to your example that blows the stack使用Python等非函数式语言。这些帖子的数量和部分学生的困惑表明，CS 教育系统在推动递归成为迭代的默认选项方面发挥了作用。递归的优雅程度取决于语言为它设计的程度。递归往往让学生感到困惑的事实更多是将递归误用于命令式语言的症状，在命令式语言中递归是循环之后的第二个 class 公民，而不是递归本身固有的任何东西。

除了学校作业、算法编码挑战和罕见的实际业务应用程序使用之外，您可能永远不需要 Python 递归。但是如果你有一把锤子，一切看起来都像钉子，所以这并不是说你不能对你看到的每一个问题应用递归，而是你可能不应该这样做' t.

递归思想非常有价值，这不是对递归作为一般工具的攻击，只是认识到Python特别不适合使用它（与大多数其他命令式语言一样）。

与递归无关，我知道你的代码只是一个演示，但 max 是一个内置函数，所以我会选择一个不同的名称。单独来看，max(list(range(999))) 看起来应该可以。

递归应用于 Python 中的列表与树

Recursion applied to lists vs trees in Python

python

recursion

big-o

space-complexity

场景 1：对平衡树（二叉树）应用递归

场景 2：对列表应用递归