2

私はC++（第一言語として）を教えてくれている友人の指導で再帰関数を書きました。しかし、私は何が起こっているのか本当に理解していません。彼は私（そしてSOコミュニティも）がマージソート関数を書くのを手伝ってくれました。

std::vector<int> mergeSort(std::vector<int> original)

//code here to create two vectors, farray and sarray, out of the 
//original std::vector<int> original ; each is half the length,
//note: if the size % 2 != 0, sarray takes the odd int

farray = mergeSort(farray);
sarray = mergeSort(sarray);

//code here merges the two into a single, final sorted std::vector

この関数では、次を割り当てます。

farray = mergeSort(farray);
sarray = mergeSort(sarray);

ここで何が起こっているのですか？パラメータとしてfarrayとsarrayを使用してmergeSortを呼び出し、値を変更します。マージソートはどこまで再帰的に実行されますか？再帰関数呼び出しまで？

4

5 に答える 5

16

関数を再帰的に呼び出すたびに、必要な情報の新しいコピーが効果的に作成され、続行されます。

「無限に」繰り返されるプログラム、つまり、リソース、通常はスタックスペース、つまりそれらのコピーが送信されるスペースがなくなるまで、プログラムを作成できます。それは次のようになります

void recur(){
    recur();
}

int main(){
    recur();
    exit(0); /* won't ever really get here.*/
}

明らかに、これはあまり便利ではないので、繰り返しの頻度にある程度の制限があるプログラムを作成する必要があります。これを管理する本当にシンプルなプログラムは次のとおりです。

#include <iostream>
using namespace std;
void recurSome(int count){
    cout << "RecurSome called with " << count << endl;
    if (count > 0){
        recurSome(count-1);
        cout << "Back at " << count << endl;
    }else{
        cout << "Bottom." << endl;
    }
    return;
}

int main(){
    recurSome(10);
    exit(0);  /* now it will get here. */
}

それをコンパイルして実行する場合は、次のように言います。

bash $ g++ -Wall -o rc recursome.cpp
bash $ ./rc

結果が得られます：

RecurSome called with 10
RecurSome called with 9
RecurSome called with 8
RecurSome called with 7
RecurSome called with 6
RecurSome called with 5
RecurSome called with 4
RecurSome called with 3
RecurSome called with 2
RecurSome called with 1
RecurSome called with 0
Bottom.
Back at 1
Back at 2
Back at 3
Back at 4
Back at 5
Back at 6
Back at 7
Back at 8
Back at 9
Back at 10
bash $

10、9などのように呼び出され、最下部に達した後、1、2、というように10に戻ることを示しています。

基本的なルールは、すべての再帰関数には、ベースケースを作成するもの、つまりそれ自体を再度呼び出すものが必要であるということです。これでは、基本ケースはcount == 0であり、実際、これを再帰的定義として記述できたはずです。

recursome：
c = 0の場合：
c> 0の場合に下部を印刷：カウントを印刷し、recursome（c-1）

数学を進めると、その種の再帰的定義がたくさん表示されます。

これは、より良い出力を備えたやや洗練されたCバージョンです。

#include <stdio.h>
#include <stdlib.h>

int max = 10;

void recurSome(int count){
    printf("RecurSome %*c Called with %d\n", max-count+1, ' ', count);
    if (count > 0){
        recurSome(count-1);
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }else{
        printf("RecurSome %*c Bottom.\n", 2*max, ' ');
        printf("RecurSome %*c Back at %d\n", max-count+1, ' ', count);
    }
    return;
}

int main(){
    recurSome(max);
    exit(0);  /* now it will get here. */
}

出力：

RecurSome   Called with 10
RecurSome    Called with 9
RecurSome     Called with 8
RecurSome      Called with 7
RecurSome       Called with 6
RecurSome        Called with 5
RecurSome         Called with 4
RecurSome          Called with 3
RecurSome           Called with 2
RecurSome            Called with 1
RecurSome             Called with 0
RecurSome                      Bottom.
RecurSome             Back at 0
RecurSome            Back at 1
RecurSome           Back at 2
RecurSome          Back at 3
RecurSome         Back at 4
RecurSome        Back at 5
RecurSome       Back at 6
RecurSome      Back at 7
RecurSome     Back at 8
RecurSome    Back at 9
RecurSome   Back at 10
于 2009-04-22T21:23:18.510 に答える
2

辞書で調べてください：

再帰: 名詞。再帰を参照

さて、真面目なことに、上記のジョークでは、再帰の定義は再帰自体の観点から与えられています。それが再帰です。

再帰アルゴリズムは、その実装がアルゴリズム自体に基づいているアルゴリズムです。このようなアルゴリズムを開発するプロセスは、最も基本的なケースから始まります。このケースの解は、事前にわかっているか、簡単に計算できます。次に、アルゴリズム自体を定義します。

簡単な例として、与えられた整数 i の n 乗を計算することは、関数 である可能性がありますpower( int number, int power )。どのように実装できますか？いろいろな意味で。最も単純なのは、ライブラリの呼び出しとそれに続くループです。または、関数自体を定義することもできます。

int power( int number, unsigned int pow )
{
   // Basic trivial case, cuts the recursion:
   if ( pow == 0 ) return 1;

   // Implement power in terms of itself:
   return number * power( number, pow-1 );
}
int main()
{
   int power = power( 2, 10 );
}

関数自体を定義しました。最も基本的なケース (n^0 = 1) から始めます。最も単純なケースでない場合は、アルゴリズム自体を表現できます。

プログラムは、power( 2, 10 )再帰呼び出しを呼び出してメインで開始し、問題をより小さなpower( 2, 9 )問題に縮小してから、より単純な問題に関して最終的な答えを作成します。

実際の呼び出しトレースは次のようになります。

power( 2, 5 )
  power( 2, 4 )
    power( 2, 3 )
      power( 2, 2 )
        power( 2, 1 )
          power( 2, 0 )    // simplest case: return 1
        return 2 * 1 -> 2  // obtain next solution in terms of previous
      return 2 * 2 -> 4
    return 2 * 4 -> 8
  return 2 * 8 -> 16
return 2 * 16 -> 32

再帰アルゴリズムを開発している間、それは通常、アルゴリズムをすでに稼働させており、新しい結果の削減/構成に取り組んでいると信じるのに役立ちました。

于 2009-04-22T22:01:24.597 に答える
2

再帰は、帰納法の原理の実際の応用として理解できます。P(n) が「1 から n までの整数の合計は n(n+1)/2 である」という意味である場合、すべての n についてステートメント P(n) を証明するには、次の 2 つのことを証明する必要があります。

  1. 基本ケース: P(n) は特定の整数に対して成り立ちます。1 = 1(1+1)/2 であるため、P(1) は真です。
  2. 帰納的な場合: P(n) が真の場合、P(n+1) も真でなければなりません。1 + ... + n + (n+1) = n(n+1)/2 + (n+1) = n(n+1)/2 + 2(n+1)/2 = (n+1) 1)((n+1)+1)/2、これはステートメント P(n+1) です。

同様に、mergeSort のような再帰関数では、次の 2 つのケースを処理する必要があります。

  1. 基本ケース:配列に 1 つの要素がある場合、それは並べ替えられます。それ以外は
  2. 再帰的なケース:配列を 2 つの小さな配列に分割し、それぞれをマージソートして、それらをマージします。

重要なのは、2 つの配列が元の配列よりも小さいことです。そうしないと、そのうちの 1 つがベース ケースにヒットすることはありません。配列はおおよそ半分に分割されるため、この場合、再帰の深さは約 log2(n) になります。

問題のコードに関する限り、3 つの問題があります。

  1. ベースケースが欠品しています。
  2. 変数 farray および sarray の再利用は厳密には必要ではなく、混乱を招く可能性があります。
  3. 作成および破棄される std::vector の数が原因で、コードは非常に遅くなります。mergeSort の最適なインターフェイスは、std::sort() 関数と同様に、入力として 2 つの vector::iterator を取ります。

新しいプログラマーは、紙と鉛筆で mergeSort を実行してみてください。

于 2009-04-22T22:52:11.867 に答える
0

再帰関数が無限にならないようにするには、それ自体を呼び出さずに戻る条件が必要です。一部のアルゴリズムでは、その状態は、データに対して呼び出しを実行する意味がなくなるポイントです。

あなたの場合、渡されたベクトルを分割し、それぞれが 1 つの項目のみを含む 2 つのベクトルになった場合、それらに対して mergeSort() を呼び出すことは理にかなっていますか? いいえ。

farray と sarray のサイズを検査し、それらを結合してその組み合わせを返す前に、いずれかまたは両方で mergeSort() を呼び出すかどうかを決定することで、これを処理できます。

1 つが 2 つの項目を持ち、1 つが 1 つの場合はどうなりますか? サイズ 2 で mergeSort() を呼び出しますが、サイズ 1 では呼び出しません。

戻る前に、mergeSort() への呼び出しが farray または sarray のいずれかで mergeSort() を呼び出さない場合、再帰は巻き戻しを開始します。

于 2009-04-22T22:00:50.073 に答える
0

あなたがやろうとしていることに関する追加情報については、マージソートのウィキペディアページをご覧ください。

補足として、パラメータとして与えられたすべてのベクトルのコピーを作成していることに注意してください。代わりに vector<> const& を使用してください。

于 2009-04-22T22:14:28.637 に答える