再帰マージソートとPython

Question

次のコードでのスタックフレーム（ない鉱山、それを研究）元のリスト（すなわち、list_）以上の再帰の間にバウンス（正しく）、およびマージルーチン。スタックフレームの流れ（つまり、Python Tutorを見ていても、どうやって彼らがどう戻ってきたのかは分かりませんが、これは私が以下に述べています）。コードがどのように戻り、質問がプログラムに続くかについての説明。

def merge(left, right): 
    if not len(left) or not len(right): 
     return left or right 

    result = [] 
    i, j = 0, 0 
    while (len(result) < len(left) + len(right)): 
     if left[i] < right[j]: 
      result.append(left[i]) 
      i+= 1 
     else: 
      result.append(right[j]) 
      j+= 1 
     if i == len(left) or j == len(right): 
      result.extend(left[i:] or right[j:]) 
      break 

    return result 

def mergesort(list_): 
    if len(list_) < 2: 
     return list_ 

    middle = len(list_)//2 
    left = mergesort(list_[:middle]) 
    right = mergesort(list_[middle:]) 

    return merge(left, right) 


list_ = [7,5,2,1,3] 

print(mergesort(list_)) 

我々は大きさ1のリストを取得するまで、私たちはヒット最初の再帰呼び出しは、（我々はなど、リストの左半分をソートし、その後、左半分の左半分にしたい、leftで、ベースケースに当たってください）。これは正常に動作します。私たちは[7,5,2,1,3]から[7,5]〜[7]に進み、ベースケースに当たった。ここまでは順調ですね。 私はスタックフレームが復帰を開始すると期待していますが、実際には何も起こりません。私はそれが7を返すと思うが、次にrightの再帰呼び出しの次のセットにジャンプする。 5が再表示されます。 5は7の直前のスタックフレームに現れました。そのため、物事は逆順に戻ります（これは良いことです）。新しいパラメータは、このように基本ケースをオフに設定し、それは奇妙な取得するのはここだ5.

を返し、5をオフに分割し、単一のリストを作成します。正しいマージステップに進みます。 は、どのようにそれがさらにrightまたはleftに再帰スキップして、「知っている」ん（私はそれをそのままでずっとそのリスト全体を、与えた）と合併するジャンプ？さらに、明示的な指示なしにマージからマージソート関数に戻す方法を知っていて、どこからピックアップするのか正確に知っていますか？誰もがこれにいくつかの光を当てることはできますか？従来のアルゴリズムのテキストやほとんどのビデオは、スタックフレームに対処していないため、ヘルプがゼロでした。

Answer 1

私はあなたの混乱は、各スタックフレームは、実行のそれ自身のポイントを持っていることを理解していないとしなければならないと思います。関数が呼び出されるたびに、フレームの実行が一時停止し、関数呼び出しのための新しいフレームが作成されます。戻ってきたら、直前のフレームが途中で止まった場所をピックアップします。コードが次にどこに向かうべきかを「知っている」中央の場所はなく、各レベルでそれ自体を処理します。あなたが説明した例のシナリオでは

、[7, 5]ためmergesort呼び出しは最初[7]と[5]にアップリストを分割し、その後、leftとrightを取得するために、順番にそれらのそれぞれに再帰。これらの再帰呼び出しのうちの2番目の呼び出しが返されると、コードの次の部分に進みます。これはコードの次の部分であるため、merge呼び出しです。

あなたは右ここに、かなりはっきりとロジックを見ることができます：

left = mergesort(list_[:middle]) 
right = mergesort(list_[middle:]) 

return merge(left, right) 

これは、この実行（および基本ケースに当たらない実行ごと）に、二回、その後、再帰的に起こっていることを示していますmerge。間違いなくそれの一部だ