4

再帰関数とメモリ スタックの間に直接的な関係はありますか。詳細については、次のコードを検討してください。

public static int triangle(int n) {
    System.out.println(“Entering: n = ” + n);
    if (n == 1) {
        System.out.println(“Returning 1”);
        return 1;
    } else {
        int temp = n + triangle(n - 1);
        System.out.println(“Returning“ + temp);
        return temp;
    }
}​

この例では、関数が返すまで、値 2、3、4、5 はどこに格納されますか? それらは LIFO(LastInFirstOut) で返されることに注意してください。これらは、メモリ スタックを処理する再帰の特殊なケースですか、それとも常に一緒になりますか?

4

4 に答える 4

3

はい、再帰関数とメモリスタックの間には直接的な関係があります。スタックサイズの制限に達し、関数がプログラムコードの一部をオーバーライドするという理由だけで、制限の高い一部の関数がプログラムをクラッシュさせるためです (これをスタックオーバーフローと呼びます)。

R: 再帰的

I: 反復

first call:
 R  |  I
|_|   |_|

second call:
 R  |  I
|_|   |_|
|_|

third call:
 R  |  I
|_|   |_|
|_|
|_|
.
.
.
n call :
 R  |  I
|_|   |_|
|_|
|_|
.
.
.
|_|

これが理にかなっているといいのですが、反復呼び出し関数は一度完了するとスタックにプッシュされ、次の呼び出しで同様の関数がロードされます。一方、再帰関数はスタックにロードされ、それ自体を呼び出してリロードします各呼び出しでスタックし、停止条件に達するとオフになり始めます (LIFO の最後の 1 つが最初の 1 つを呼び出します)。

あなたの問題に具体的に言うと、停止条件が満たされたときにあなたが言ったn値がメモリに保持され、最後の関数がnを表示し、終了して、それを呼び出したばかりの関数に手を渡します。 n の独自の値も表示し、最初の関数が呼び出されるまで同じことが繰り返されますが、反復関数はカウンター n の値を表示します (1 つの変数のみが使用され、その値を変更しています)。

以下は、stackoverflow に関する良い記事です。

非常に深いまたは無限の再帰 主要な記事: 無限の再帰 スタック オーバーフローの最も一般的な原因は、過度に深いまたは無限の再帰です。末尾呼び出しの最適化を実装する Scheme などの言語では、特定の並べ替えの無限再帰 (末尾再帰) をスタック オーバーフローなしで実行できます。これが機能するのは、末尾再帰呼び出しが追加のスタック スペースを占有しないためです。

http://en.wikipedia.org/wiki/Stack_overflow

于 2012-12-12T22:44:05.420 に答える
2

これが C++ クラスのメソッドであると仮定すると、triangle(n) を呼び出すと、次のようなデータがスタックにプッシュされます。

  • function code
  • int *returnAddress
  • int n

関数が戻るまで戻り値が割り当てられない場所。RS Shaw は、 Call Stack ウィキペディアのページ ( こちら)に素敵な画像の例を提供しています。

このデータは、再帰ごとに 1 回コール スタックの一番上にプッシュされるため、triangle(n) への最後の呼び出しのコードが一番上になります。格納される値*returnAddressは、再帰を巻き戻すために結果を格納する必要があるメモリ内の場所です。

つまり、結果自体 (たとえば、三角形 (1) の場合は 1、三角形 (2) の場合は 3) はfunction code、メモリ内の特定の名前付きの場所ではなく、スタックの一部のどこかに配置されます。デバッガーを実行する場合、関数コードreturnAddress内にブレークポイントを配置することで、その場所を追跡できるはずです。triangle

ところで、これは再帰の特殊なケースではありません。これは古典的な教科書のケースです。

于 2012-12-12T23:01:54.883 に答える
0

一時変数 n はスタック上にあり、呼び出し n-1 へのパラメーターと同様に戻りアドレスになります。これらはすべて同じスタックにあります。

于 2012-12-12T22:31:08.133 に答える
0

QuentinQK が説明したように、ローカル変数 n は関数の戻りアドレスと同様にスタック スペースを消費し、(しばらくの間) 戻り値と再帰関数に渡されたすべてのパラメーターがスタック上のスペースを消費します。そして、これは各再帰レベルで発生します。したがって、再帰がどれだけ深くなるか (この関数が自分自身を呼び出す頻度) によって、最終的に再帰されるスタックの量とバーストするかどうかに依存します。

まさにその理由で、シムの最終状態を持つことが不可欠です。あなたの例では、このif (n==1)' condition where the recursion is stopped when that value is reached. It only works along with then-1in the parameter list of the recursive call of三角形です。

しかし、あなたは本当に何を知りたいですか？

于 2012-12-12T22:45:38.683 に答える