3

私は、C での再帰を扱う章を含む本を読んでいます。それは 99 ボトルの歌をログに出力します。コードは次のとおりです。

void singTheSong (int numberOfBottles) {

    if (numberOfBottles == 0) {
        printf("There are no more bottles left.\n");
    } else {
        printf("%d bottles of bear on the wall, %d bottles of beer.\n", numberOfBottles,
               numberOfBottles);

        int oneFewer = numberOfBottles - 1;

        printf("Take one down, pass it around, %d bottles of beer on the wall.\n", oneFewer);

        singTheSong(oneFewer); 
    }
}

int main(int argc, const char * argv[])
{

    singTheSong(99);
    return 0;
}

出力は、歌がどのように歌われるかのように読み取れます。私が理解に苦しんでいるのは、numberOfBottles変数がその値をどのように変更するかということです。変数で1 が減算されることがoneFewerわかりますが、これがどのように機能しているかを正確に理解できていません。ログには、「壁に 99 本のクマ、99 本のビール。1 本を降ろして回し、壁に 98 本のビール」と書かれているように思えます。numberOfBottles値がどのように変化するのか、したがってoneFewerボトルの数をどのように追跡するのかはわかりません。もう 1 つ質問があります。このトピックに関する私の混乱は、プログラミングを続けるのに悪い兆候ですか? ここまで釘付けでした。

4

6 に答える 6

8

鍵はここにあります：

    int oneFewer = numberOfBottles - 1;
    singTheSong(oneFewer);

への新しい呼び出しsingTheSongが生成されます。ここで、は 99 ではなく 98 です。その関数は、値 98 でnumberOfBottlesのローカル コピーを取得します。numberOfBottles

Stack                                  numberOfBottles
------------------------------------------------------
singTheSong                            99
  singTheSong                          98
    singTheSong                        97
      singTheSong                      96
        ...                            ...
          singTheSong                  1
            singTheSong                0

numberOfBottlesゼロになるまでに、100 個のネストされた呼び出しsingTheSongがスタックに置かれます。最後に、関数は再帰を行わずに戻り、待機していたスタックのすべてのコピーが一度に 1 つずつ戻ります。

于 2013-05-20T01:01:40.240 に答える
2

初めてsingTheSongというnumberOfBottles方です99。

次に、singTheSong(numberOfBottles-1)( 99 - 1 = 98) を呼び出します。これはsingTheSong(numberOfBottles-1)、新しいボトル数、つまりで呼び出します98 - 1 = 97。

このプロセスは、基本ケースに到達するまで繰り返されます。

于 2013-05-20T00:58:53.647 に答える
2

一枚の紙を取り、各呼び出しごとにコール スタックを描画し、引数の値と戻りアドレスを記録します (巻き戻されることがわかるように)。従う方が簡単なはずです。

実行は、最後 (基本ケース)elseを除いて、常にブロックに入ります。これは、 に達するまで数値が減少することを意味します。if0

于 2013-05-20T00:57:52.053 に答える
2

最初に最後の質問に答えます。いいえ、これは必ずしもあなたのプログラミング キャリアが運命づけられているという意味ではありません。再帰を理解することは重要ですが、その優れた機能的使用法 (ウォーキング ツリーとグラフがすぐに思い浮かびます) のほとんどは、深く理解する必要のないライブラリに既に実装されています。関数型プログラミングに着手すると、それはより重要になりますが、それまでに、それを十分に理解することができます.

あなたが理解していないことを示しているのは、関数の性質とコールスタックが何をするかです。それを学ぶことは重要であり、再帰はそれを行うための良い方法です。

再帰に関する問題は、コール スタックで同じ関数が多数呼び出されることです。この場合、99 から開始すると、はい、oneFewer= 98 になります。しかし、関数を終了する前にsingTheSong、oneFewer、つまり 98 を渡すことを呼び出します。そして、97singTheSongの値で呼び出します。oneFewer

これにより、同じ関数の 100 個のインスタンスがすべてコール スタックに積み上げられます。100 番目の曲で、「ボトルが残っていません」と出力し、関数を終了します。次に、「1 ボトル」の関数が完了したので終了し、「2 ボトル」関数を完了させます。元の関数が完了するまで、コール スタック全体で同様の処理が行われます。

于 2013-05-20T01:04:12.050 に答える
2

理解しておくべきことは、関数 singTheSong が自分自身を呼び出しているということです。したがって、関数 main は singTheSong(99) を呼び出します。この関数はいくつかの情報を出力し、変数 oneFewer に 99 - 1 を設定してから、oneFewer の値を指定して singTheSong を再度呼び出します。なので今回渡す値は99ではなく98です。

新しい関数は singTheSong の別のインスタンスです。以前に呼び出された singTheSong については何も知りません。それが知っているのは、値 98 が与えられたということだけであり、何かを出力し、98-1 を oneFewer に貼り付けてから、singTheSong をもう一度呼び出す必要があります。

プログラムが 0 になるまでに、singTheSong のインスタンスは実際には 99 個になります。しかし、ゼロで呼び出されると、再帰する代わりに、「ボトルが残っていません」と出力されます。その後、プログラムは 99 のケースすべてを元に戻し、最後に終了します。したがって、0 は基本ケースであり、すべての再帰アルゴリズムが到達する基本ケースを持つことが重要です。

これをもっと理解したい場合は、printf("%d %d \n",oneFewer, numberOfBottles); を入れてみてください。再帰呼び出しの後。

コンピューターをクラッシュさせたい (そしてこのサイトの名前を確認したい) 場合は、if ステートメントと「ボトルが残っていない」という基本ケースを削除してみてください。

于 2013-05-20T01:07:44.607 に答える
1

「1つ降ろして回してください」という発言の後、

singTheSong(oneFewer);

これは、その特定の反復でのボトル数の値を保持する変数です。numberOfBottles は最初 99 で、次に oneFewer が 98 に割り当てられます。次に、oneFewer = 98 が singTheSong に渡されます。今回、numberOfBottles として参照される引数は、前の繰り返しのoneFewerと同じ値を持ちます。この反復では、oneFewer は 97 の値を取得し、このサイクルは、oneFewer が 0 で、singTheSong に渡される基本ケースに到達するまで続きます。singTheSong はその値を取得し、ifケースに到達したことを認識して停止します。

于 2013-05-20T01:04:12.763 に答える