时间戳

首页 > 解决方案 > 递归应用于 Python 中的列表与树

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

问题描述

我对递归的主要关注是 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 时递归何时是一般的好选择。

标签： pythonrecursionbig-ospace-complexity

解决方案

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

您可以创建基于生成器的蹦床函数，如本博文所示：

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)

推荐阅读