递归应用于 Python 中的列表与树 [英] Recursion applied to lists vs trees in Python

问题描述

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

My main concern with recursion is the recursion limit in Python, which I think is 1000. Taking this into account, I want to discuss two scenarios:

例如搜索树中的最大值:

For example, to search the maximum value in a tree:

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)个元素而不会达到调用限制.对我来说，这不是一个真正的限制，所以我认为我们可以在这里使用递归.

Here, the maximum number of calls in the stack at any given time will be the height of the tree, which is log_2(n) where n is the number of elements in the list. Given that the limit in Python is 1000 calls, the tree could store up to 2^1000 (or 2^999) elements without reaching the call limit. For me, that is not a real limitation so I assume we are OK using recursion here.

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

A dummy example would be computing the max of a list, so that we return the max between the head of the list and the result of the same function over the rest of the list:

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

So my understanding is that for lists recursion is not a reasonable option, since it cannot generally process lists larger than 999 (or even less, depending on the stack trace).

现在，我的问题:

1. 使用递归来处理平衡树是否合理?
2. 对于大多数问题，它不是一个选项(列表、非平衡树等)，这是真的吗?
3. 这里还有什么我应该考虑的吗?我只是想了解更多关于使用 Python 时递归何时是最佳选择的信息.

推荐答案

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

Firstly, bear in mind that a language is not the same as the implementation of a language. The call stack size in Python varies by implementation. The limit of 1000 applies to CPython but not necessarily all implementations.

使用递归来处理平衡树是否合理?

Is it reasonable to use recursion to process balanced trees?

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

Recursion is reasonable for balanced trees. As you've described quite clearly, the maximum call stack depth is a logarithmic factor on the size of the structure. You'd need a huge input to blow the stack.

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

With a list or degenerate unbalanced tree, recursion is inappropriate because the maximum call stack depth is linear on the structure length.

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

That said, I don't find it necessary to use self-balancing trees often in Python. Most work is done on lists and dicts, occasionally nested and recursively defined. The fact that recursion happens to be a good fit for structures like trees doesn't imply that it's widely applicable in general in Python.

对于大多数问题，它不是一个选项(列表、非平衡树等)，这是真的吗?

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

是的，但是 CPython 中的设计禁止递归.Python 是不是函数式语言.CPython 不支持尾调用优化并且从不"将.

Yes, but recursion is inhibited by design in CPython. Python is not a functional language. CPython doesn't support tail call optimization and "never" will.

Guido 有一篇很棒的博文 为 CPython 辩护反递归设计.无论您是否同意这种设计，工具通常都应该按预期使用，而不是按照人们希望的方式使用.

Guido has a great blog post that defends CPython's anti-recursion design. Regardless of whether you agree with this design or not, tools should generally be used as intended, not as one wishes them to be.

在紧要关头，Python(作为一种多范式语言)可以支持以函数式风格编写的代码，并且有解决方法长递归工作，但这并没有改变它们是变通方法的事实.

In a pinch, Python (as a multi-paradigm language) can support code written in a functional style and there are workarounds to make long recursion work, but that doesn't change the fact that they're workarounds.

这里还有什么我应该考虑的吗?我只是想更多地了解在使用 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 中的函数调用比迭代具有更多的开销(时间和空间)，因此即使结构大小适合调用堆栈或您使用技巧来支持深度递归，也需要考虑性能问题.

Function calls in CPython have more overhead (time and space) than iteration, so there are performance issues to consider even when the structure size fits in the call stack or you use a trick to support deep recursion.

使用setrecursionlimit 是不安全的，几乎没有必要.大多数语言都没有这样的选项.增加它意味着您冒着操作系统杀死 CPython 解释器的风险.当然，摆弄限制对于快速编写脚本和调试很有用，但这不是通用的解决方案.

Using setrecursionlimit is unsafe and almost never necessary. Such an option is not available in most languages. Increasing it means you're running the risk of the operating system killing the CPython interpreter. Sure, fiddling with the limit can come in handy for quick scripts and debugging, but it's not a general solution.

recursion 标签中充斥着来自善意的 CS 学生负责解决递归问题类似于你的例子堆栈 使用 Python 和其他非函数式语言.这些帖子的数量和学生的困惑表明 CS 教育系统在推动递归作为迭代的默认选项方面发挥了作用.递归仅与语言为其设计的程度一样优雅.递归往往让学生感到困惑这一事实更多地是将其误用于命令式语言的一种症状，在这种语言中，递归是循环后的二等公民，而不是递归本身固有的任何东西.

The 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 using Python and other non-functional languages. The quantity of these posts and the confusion on the part of the students suggests that the CS education system has a role in pushing recursion as the default option for iteration. Recursion is only as elegant as the extent to which the language was designed for it. The fact that recursion tends to be confusing to students is more a symptom of the misapplication of it to imperative languages where recursion is a second-class citizen after loops than anything inherent in recursion itself.

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

You'll probably never need recursion in Python other than school assignments, algorithm coding challenges and the rare practical business application use. But if you have a hammer, everything looks like a nail, so this isn't to say you can't apply recursion to each and every problem you see, it's that you probably shouldn't.

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

Recursive thinking is very valuable, and this isn't an attack on recursion as a tool in general, just recognizing that Python is particularly ill-suited for using it (as are most other imperative languages).

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

Unrelated to recursion and I understand your code is just a demonstration, but max is a builtin function, so I'd pick a different name. Taken alone, max(list(range(999))) looks like it should work.

这篇关于递归应用于 Python 中的列表与树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！