不明白为什么我在这里获得最大的递归深度

Question

我有这样的功能：

def sort(lst, beg, end):
    mid = (beg + end)/2
    sort(lst, beg, mid)
    sort(lst, mid, end)
    i = 0
    j = 0
    for l in range(beg, end):
        if j > end - mid or (i <= mid - beg and lst[beg + i] < lst[mid + j]):
            lst[l] = lst[beg + i]
            i = i + 1
        else:
            lst[l] = lst[mid + j]
            j = j + 1

输入为 ： sort（[1,5,6,6,3,1,5,4,3,3,4,5,6,7,8,5,3,2,4,5]， 1， 10）

作为输出：

RuntimeError: maximum recursion depth exceeded

我该如何解决这个问题？

Answer 1

您缺少一个将阻止您递归的条件。在当前的实现中，您将无限期地继续。

例如：

def sort(lst, beg, end):
    if end - beg <= 1:
        return
    mid = (beg + end)/2
    sort(lst, beg, mid)
    sort(lst, mid, end)
    # rest of code

Answer 2

没有什么可以阻止递归。每次调用排序时，它都会调用自己 2 次。应该有一个条件语句。