再帰的なmergeflowの最大再帰を超過

Question

私は、オンラインクラスの再帰的なマージフローを実装しようとしており、小さな問題があります。

分割統治は、このような正常に動作するコード：

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 

これは最大の再帰の深さを超えています。私が知る限り、私はロジックを変更せず、これをデバッグするのに問題があります。もちろん、ここに潜んでいる微妙なバグではありませんが、私の人生では、なぜ最初のバージョンが動作するのか、2番目のバージョンではないのか分かりません。

Answer 1

私はこの問題は、お使いのベース・ケースということであるかなり確信している：あなたの第二の再帰呼び出しは半ばに1を追加しない場合

if hi <= lo: 
    return 

が発生することはありません。あなたは無限の再帰を取得するので、あなたは、まったく同じ値で__recursive_mergesort(arr, aux, mid, hi)に渡す

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

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

：我々はmid結果を得るために私達の計算それではポイント

hi = 1; lo = 0; mid = 0 

を取得、考えてみましょう。