2

我正在尝试计算列表的长度。当我在 cmd 上运行它时，我得到：

RuntimeError：比较超过最大递归深度

我认为我的代码没有任何问题：

def len_recursive(list):
    if list == []:
        return 0
    else:
        return 1 + len_recursive(list[1:])
4

6 回答 6

3

不要使用递归，除非你可以预测它不会太深。Python 对递归深度的限制非常小。

如果你坚持递归，有效的方法是：

def len_recursive(lst):
    if not lst:
        return 0
    return 1 + len_recursive(lst[1::2]) + len_recursive(lst[2::2])
于 2013-01-14T20:59:24.533 回答
2

Python 中的递归深度是有限的，但可以增加，如本文所示。如果 Python 支持尾调用优化，则此解决方案适用于任意长度的列表：

def len_recursive(lst):
    def loop(lst, acc):
        if not lst:
            return acc
        return loop(lst[1:], acc + 1)
    return loop(lst, 0)

但事实上，您将不得不使用较短的列表和/或增加允许的最大递归深度。

当然，没有人会在现实生活中使用这个实现（而不是使用len()内置函数），我猜这是递归的学术示例，但即便如此，这里最好的方法是使用迭代，如图所示@poke 的回答。

于 2013-01-14T21:01:42.803 回答
2

正如其他人所解释的，您的功能存在两个问题：

  1. 它不是尾递归的，所以它只能处理列表，只要sys.getrecursionlimit.
  2. 即使它是尾递归的，Python 也不会进行尾递归优化。

第一个很容易解决。例如，请参阅 Óscar López 的回答。

第二个很难解决，但并非不可能。一种方法是使用协程（基于生成器）而不是子例程。另一种方法是不实际递归调用函数，而是返回具有递归结果的函数，并使用应用结果的驱动程序。有关如何实现后者的示例，请参阅Paul Butler在 Python 中的尾递归，但这就是您的情况。

从 Paul Butler 的tail_rec函数开始：

def tail_rec(fun):
    def tail(fun):
        a = fun
        while callable(a):
            a = a()
        return a
    return (lambda x: tail(fun(x)))

这不能作为他的案例的装饰器，因为他有两个相互递归的函数。但在你的情况下，这不是问题。因此，使用 Óscar López 的版本：

@tail_rec
def tail_len(lst):
    def loop(lst, acc):
        if not lst:
            return acc
        return lambda: loop(lst[1:], acc + 1)
    return lambda: loop(lst, 0)

现在：

>>> print tail_len(range(10000))
10000

多田。

如果您真的想使用它，您可能想要制作tail_rec一个更好的装饰器：

def tail_rec(fun):
    def tail(fun):
        a = fun
        while callable(a):
            a = a()
        return a
    return functools.update_wrapper(lambda x: tail(fun(x)), fun)
于 2013-01-14T21:13:54.230 回答
1

您的异常消息意味着您的方法被递归调用太频繁，因此您的列表可能太长而无法像这样递归地计算元素。您可以简单地使用迭代解决方案来做到这一点：

def len_iterative(lst):
    length = 0
    while lst:
        length += 1
        lst = lst[1:]
    return length

请注意，这很可能仍然是一个糟糕的解决方案，因为lst[1:]会继续创建列表的副本。所以你最终会得到len(lst) + 1列表实例（长度0为len(lst)）。直接使用内置可能是最好的主意len，但我想这是一项任务。

于 2013-01-14T21:01:21.557 回答
1

想象一下，您正在使用一叠纸来运行它。你想计算你有多少张纸。如果有人给你 10 张纸，你拿第一张纸，把它放在桌子上，抓起下一张纸，放在第一张纸旁边。你这样做了 10 次，你的桌子已经满了，但你已经把每张纸都摆好了。然后你开始计算每一页，在你计数时回收它，0 + 1 + 1 + ... => 10。这不是计算页面的最佳方法，但它反映了递归方法和 python 的实现。

这适用于少量页面。现在想象有人给了你 10000 张纸。很快，您的办公桌上就没有空间来布置每一页了。这基本上就是错误消息告诉您的内容。

最大递归深度是表格可以容纳的“多少张”。每次调用 python 时都需要保留“1 + 递归调用的结果”，以便在所有页面都布置好后，它可以返回并计算它们。不幸的是，在最后的计数发生之前你的空间已经用完了。

如果你想递归地学习，因为你想在任何合理的情况下使用 len() ，只需使用小列表，25 应该没问题。

如果某些系统支持尾调用，则它们可以处理大型列表

于 2013-01-14T21:06:51.593 回答
0

Python 没有优化尾递归调用，因此使用这种递归算法不是一个好主意。您可以使用sys.setrecursionlimit()调整堆栈，但这仍然不是一个好主意。

于 2013-01-14T20:57:56.083 回答