python - 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:对列表应用递归

一个虚拟示例是计算列表的最大值，以便我们返回列表头部与列表其余部分相同函数的结果之间的最大值:

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(甚至更少，取决于堆栈跟踪)的列表。

现在，我的问题:

1. 使用递归处理平衡树是否合理？
2. 对于大多数问题来说，它确实不是一个选择(列表、非平衡树等)吗？
3. 这里还有什么我应该考虑的吗？我只是想了解更多关于使用 Python 时递归什么时候是好的选择。

Answer 1

首先，请记住，语言与语言的实现不同。 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(作为一种多范式语言)可以支持以函数式风格编写的代码，并且有workarounds to make long recursion work ，但这并不能改变它们是解决方法的事实。

---

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 中的函数调用比迭代具有更多的开销(时间和空间)，因此即使结构大小适合调用堆栈或使用技巧来支持深度递归，也需要考虑性能问题。

Using setrecursionlimit is unsafe and almost never necessary 。大多数语言都没有这样的选项。增加它意味着您将面临操作系统终止 CPython 解释器的风险。当然，摆弄限制可以方便地进行快速脚本和调试，但这不是通用的解决方案。

recursion标签充斥着来自善意的计算机科学学生的问题，他们的任务是用递归解决问题 similar to your example that blows the stack使用Python和其他非函数式语言。这些帖子的数量和学生的困惑表明，计算机科学教育系统在插入递归作为迭代的默认选项方面发挥了作用。递归的优雅程度取决于语言为其设计的程度。递归往往会让学生感到困惑，这一事实更多地表明它被误用在命令式语言中，在命令式语言中，递归是循环之后的二等公民，而不是递归本身固有的任何东西。

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

递归思维非常有值(value)，这并不是对递归作为一般工具的攻击，只是认识到 Python 特别不适合使用它(就像大多数其他命令式语言一样) )。

---

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