递归合并流超过最大递归

Question

我正在尝试为在线 class 实现递归合并流，但遇到了一个小问题。

分而治之的代码像这样工作得很好：

def __recursive_mergesort(arr, aux, lo, hi):
    if hi <= lo:
        return
    mid = lo + (hi - lo) // 2

    __recursive_mergesort(arr, aux, lo, mid)
    __recursive_mergesort(arr, aux, mid + 1, hi)
    # Call merge here...


def mergesort(x):
    aux = [0] * len(x)
    __recursive_mergesort(x, aux, 0, len(x) - 1)
    return x

然而，当我这样做时：

def __recursive_mergesort(arr, aux, lo, hi):
    if hi <= lo:
        return
    mid = lo + (hi - lo) // 2

    __recursive_mergesort(arr, aux, lo, mid)
    __recursive_mergesort(arr, aux, mid, hi)
    # Call merge here...


def mergesort(x):
    aux = [0] * len(x)
    __recursive_mergesort(x, aux, 0, len(x))
    return x

这超出了最大递归深度。据我所知，我没有改变逻辑，而且我在调试时遇到了麻烦。当然这里潜伏着一个微妙或不那么微妙的错误，但就我的生活而言，我无法弄清楚为什么第一个版本运行而不是第二个版本。

Answer 1

我很确定问题在于您的基本情况：

if hi <= lo:
    return

如果您的第二次递归调用没有将 1 添加到 mid，则永远不会发生。考虑一下，我们进入正题

hi = 1; lo = 0; mid = 0

那么我们对 mid 的计算结果是：

In [21]: hi = 1; lo = 0; mid = 0

In [22]: lo + (hi - lo) // 2
Out[22]: 0

然后将其传递给具有完全相同值的 __recursive_mergesort(arr, aux, mid, hi)，因此您将获得无限递归。

递归合并流超过最大递归

recursive mergeflow max recursion exceeded

python

recursion

mergesort