0

ここにマージソートで分割するコードがあります..実際に再利用がどのように機能するかを理解できません!!

マージソートパーティション 

void partition(int arr[], int low, int high){
    int mid;
    if(low < high){
         mid = (low + high)/2;
         partition(arr, low, mid);
         partition(arr, mid + 1, high);
         mergeSort(arr, low, mid, high);
    }
}

実際、多くの再帰的な問題でめちゃくちゃになっていて、システムスタックが再帰でどのように機能するかを理解できません...初心者です..

4

2 に答える 2

2

再帰関数をより簡単にしようとします。たとえば、階乗疑似コードの小さな例を見てみましょう。

int fact(n)
{
  if(n==1 || n==0) return 1;
  else
  return (n*fact(n-1));
}

これにより、関数のスタックが作成されます。これを呼び出すとfact(3)、次のようなスタックが作成されます。

fact(0)
fact(1)
fact(2)
fact(3)

各関数がスタックにプッシュされます。最初fact(3)に呼び出されます。fact(3)を呼び出しますfact(2)。パスの後 -

スタックの構築:

                                               fact(0)
                                   fact(1)     fact(1)
                       fact(2)     fact(2)     fact(2)
empty --> fact(3) ---> fact(3) --> fact(3) --> fact(3)

これで、関数は をキャッチn=0して返します1。これで、関数が飛び出し始めます。

スタック :

   fact(0) -----> (returns 1) = 1
                    fact(1) -----> (returns 1) * 1 (1's popped out)
                                     fact(2) -----> (returns 2) * 1 (1 is actually 1*1)
                                                      fact(3) -----> (returns 3) * (2 = 2*1*1)
                                                                                          ----->6

EDIT：機能的にポップを追加しました。ソート スタックについては、@P0W の回答をご確認ください。

小さな例を取り上げて、スタックを構築してみてください。次に、複雑なものに進みます。練習が鍵であることを忘れないでください。これが、再帰関数がスタックとして機能する方法です。

それが役に立てば幸い。:)

于 2013-08-24T16:41:23.820 に答える