0

我正在参加 Coursera 的在线课程“算法：设计与分析，第 1 部分”，并且刚刚完成了第二个作业。但是在我做的过程中，我无法解释一个由python运行时错误引起的现象。

我不应该分发解决方案代码......所以我只写一些摘录。

def quick_sort_count (arr, index, median=False):
     # SOME OPERATIONS
     ......
     # Termination
     if len(arr)==0 or len(arr)==1:
         return arr, 0
     ........
     arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
     arr[i:], t2 = quick_sort_count(arr[i:], index, median)
     return arr, len(arr)+t1+t2-1

该程序应分析具有 10,000 个唯一编号的数据文件，并计算快速排序中有多少“比较”。该问题包含三个部分：使用第一个元素作为比较的枢轴；使用最后一个；并使用“中位数”。

奇怪的是，我可以通过单独运行任何一个问题来得到正确的答案。但我不能在一个函数中同时运行这三个函数，例如

def main():
    # READING THE FILE
    ......
    _,result1 = quick_sort_count(arr1, 0)
    _,result2 = quick_sort_count(arr2, -1)
    _,result3 = quick_sort_count(arr3, 0, True)

如果我这样做了，那么将出现“RuntimeError：超出最大递归深度”。喜欢的东西

....
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 43, in quick_sort_count
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 43, in quick_sort_count
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 43, in quick_sort_count
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 43, in quick_sort_count
arr[:i-1], t1 = quick_sort_count(arr[:i-1], index, median)
  File "/Users/c/algorithm/quick_sort.py", line 33, in quick_sort_count
arr = swap(arr, index, 0)
RuntimeError: maximum recursion depth exceeded

“swap”只是一个简单的操作，改变了arr[index]和arr[0]的位置，这是第二个问题的要求——“使用最后一个元素作为pivot元素并将其交换到之前的第一个元素排序”。

如果我通过进一步增加递归限制

import sys
sys.setrecursionlimit(100000)

那么第 2 题和第 3 题就会有错误的答案。

有人能告诉我为什么会这样吗？非常感谢！

4

1 回答 1

3

由于您还没有发布完整的代码，这里有一些关于如何克服 python 递归限制的一般建议。

通用递归函数具有以下结构：

def foo:
    if termination-condition
        return value
    else
        new-value = some-calculations
        return foo(new-value)

第一步是让你的函数尾递归，即消除else分支中的计算，并带入表格

def foo:
    if termination-condition
        return value
    else
        return foo(some-calculations)

在支持尾递归优化的语言中就足够了，在 python 中你必须更进一步。与其立即进行递归调用return foo(...)，不如返回一个“thunk”，它基本上是对您打算做什么的描述或承诺。在 python 中，thunk 可以写成匿名lambda函数：

def foo:
    if termination-condition
        return value
    else
        return lambda: foo(some-calculations)

当然，您将需要另一个中间函数来使用从返回的值foo，如果给出 thunk，则执行它直到返回终端（非函数）值：

def foo-interface:
    # get a thunk or a terminal
    t = foo()  
    # while it's a thunk...
    while callable(t):
        t = t() # ...carry it out
    # return the terminal
    return t

例子

让我们有以下简单的阶乘实现，它在大参数上失败：

def fac(n):
    return 1 if n < 2 else n * fac(n - 1)

> fac(3000)
> RuntimeError: maximum recursion depth exceeded

将其转换为尾递归...

def f(n, acc=1):
    return acc if n < 2 else f(n - 1, acc * n)

...应用 thunk 转换...

def f(n, acc):
    return acc if n < 2 else lambda: f(n - 1, acc * n)

...并将其包装在接口函数（消费者）中...

def fac(n):

    def f(n, acc):
        return acc if n < 2 else lambda: f(n - 1, acc * n)

    t = f(n, 1)
    while callable(t):
        t = t()
    return t

有用！ 

> fac(3000)
> 41493596034....

这种技术被称为“蹦床”。不知道这对您的特定情况是否有帮助（因此是 CW），但我想这是值得了解的事情（并且偶然给您的教授留下深刻印象））。

装饰器

这种尾递归可以写成装饰器。这里lambda给出了一个使用类而不是很好的解释。

于 2013-02-12T09:47:10.753 回答