CodeGym /Java Course /モジュール 2: Java コア /終了条件。スタックオーバーフローエラー

終了条件。スタックオーバーフローエラー

モジュール 2: Java コア
レベル 10 , レッスン 1
使用可能

終了条件のない再帰コードの例

再帰的問題をもう一度見てみましょう。例として、フィボナッチ数の計算を考えてみましょう。フィボナッチ数列は、最初の 2 つの数値が 0 と 1 であり、後続の各数値が前の 2 つの数値の合計に等しい数値シーケンスであることを誰もが思い出すでしょう。

これらの数値を計算して表示するコードを書いてみましょう。


public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacci(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }
}
    

再帰的printFibonacciメソッドを最初に呼び出す前に、シーケンスの最初の 2 つの数値 (0 と 1) を出力します。再帰的メソッドではパラメータ自体ではなく、入力パラメータの合計のみが表示されるため、これを行う必要があります。

コードは問題ないようです。2 つの数値を取得し、その合計を計算して、コンソールに出力し、printFibonacciメソッドを再帰的に呼び出します。以前の番号 (previous) と現在の番号 (current) を引数として渡します。

実際、コードには 2 つのエラーがあります。コードを実行するとそれらを確認できます。

最初のエラーは、long型のオーバーフローです。シーケンスの 104 番目の数値は負であり、long型がオーバーフローしたことを示しています。

2 番目のエラーは異なります。およそ 12,000 個の数値を計算すると、次の結果が得られます。

スレッド「メイン」java.lang.StackOverflowError での例外

ここで、Java のメソッド呼び出しスタックが何であるかを思い出してください。Java マシンはすべての関数呼び出しの記録を保持します。これを行うには、スタックと呼ばれる特別な種類のコレクションを使用します。ある関数が別の関数を呼び出すと、Java マシンは新しい StackTraceElement をスタックにプッシュします。関数が終了すると、この要素はスタックから削除されます。したがって、スタックには、関数呼び出しスタックの現在の状態に関する最新の情報が常に格納されます。StackTraceElement のドキュメントには、「アプリケーションの再帰が深すぎるためにスタック オーバーフローが発生した場合にスローされる」と記載されています。実行中の JVM には、メソッド呼び出しスタックを保存するための特別なメモリ領域があります。このメモリ領域のサイズは、OS と JVM の設定によって異なります。メソッド呼び出しスタック自体に加えて、プリミティブ変数 (メソッド パラメーターの特定の値) と参照変数のアドレス (「ヒープ」と呼ばれるメモリー領域内) は、この特別なメモリー領域に保管されます。コール スタックへのアクセスは、LIFO 原則に従います。

終了条件を含む修正された例

コード内の 2 番目の問題を修正することから始めましょう。

問題を正面から解決してみましょう。スタックが小さすぎる場合は、スタックを大きくしましょう。これを行うには、「-Xss」フラグを使用して JVM を起動し、スタックに割り当てるメモリ量を指定します。5メガバイトを割り当ててみましょう。IDEA では次のようになります。

出力の長さを伸ばすことができました。約 12,000 個の数値に制限されるのではなく、49,000 個を超える数列の数値を計算できるようになりました。しかし、ある時点で依然としてStackOverflowError が発生します。

スタックのサイズを増やすこともできますが、根本的な問題は解決されません。それでは、論理の問題を探してみましょう。再帰が停止する時点が必ず存在します。言い換えれば、再帰メソッドがいつ呼び出されなくなり、呼び出しスタックが巻き戻されるかを決定する何らかの条件が必要です。このような条件を定義するには、目的を明示的にしましょう。数値がInteger.MAX_VALUEより小さい限り、フィボナッチ数列を表示します。

この条件を考慮する新しいprintFibonacciWithConditionメソッドを作成しましょう。そして、新しく修正されたメソッドを main メソッドで呼び出します。


public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
//        printFibonacci(0, 1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacci(long penultimate, long previous) {
        long current = penultimate + previous;
        System.out.println(current);
        printFibonacci(previous, current);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
    }
}
    

コードを実行すると、出力が数値 1836311903 で終わることがわかります。この数値の前の数値は 1134903170 です。これらの数値の合計は 2_971_215_073 で、これは実際に Integer.MAX_VALUE (2_147_483_647) より大きくなります

この変更により、ロングオーバーフローのバグが自動的に修正されました。さらに多くの系列を計算する必要がある場合は、BigIntegerなどの他のデータ型を使用する必要があります。

再帰的な降下と巻き戻し

コードがどのように実行されるかを段階的に分析してみましょう。これを行うには、echoメソッドを追加し、 printFibonacciWithConditionメソッドの再帰呼び出しの前後でそれを呼び出します。


public class Fibonacci {
    public static void main(String[] args) {
        System.out.println(0);
        System.out.println(1);
        printFibonacciWithCondition(0, 1);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        echo(true, penultimate, previous);
        System.out.println(current);
        printFibonacciWithCondition(previous, current);
        echo(false, penultimate, previous);
    }

    private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
        if (isBeforeRecursiveCall) {
            System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
        } else {
            System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
        }
    }
}
    

プログラムでは次の出力が得られます。

0
1
引数付きのメソッド呼び出し前: 0、1。現在の番号 = 1
引数付きのメソッド呼び出し前: 1、1。現在の番号 = 2
引数付きのメソッド呼び出し前: 1、2。現在の番号 = 3
引数付きのメソッド呼び出し前: 2、3。 現在の番号 = 5
引数付きのメソッド呼び出し前: 3、5。 現在の番号 = 8
引数付きのメソッド呼び出し前: 5、8。 現在の番号 = 13
引数付きのメソッド呼び出し前: 8、13。 現在の番号 = 21
引数付きのメソッド呼び出し前: 13、21。現在の番号 = 34
引数付きのメソッド呼び出し前: 21、34。現在の番号 = 55
引数付きのメソッド呼び出し前: 34、55。現在の番号 = 89
引数付きのメソッド呼び出し前: 55、 89. 現在の数 = 144
引数付きのメソッド呼び出し前: 89、144。現在の数値 = 233 引数
付きのメソッド呼び出し前: 144、233。現在の数値 = 377
引数付きのメソッド呼び出し前: 233、377。現在の数値 = 610
引数付きのメソッド呼び出し前: 377、 610. 現在の数値 = 987
引数付きのメソッド呼び出し前: 610、987。 現在の数値 = 1597
引数付きのメソッド呼び出し前: 987、1597。 現在の数値 = 2584 引数
付きのメソッド呼び出し前: 1597、2584。 現在の数値 = 4181
メソッド前引数付きのメソッド呼び出し: 2584、4181。現在の番号 = 6765
引数付きのメソッド呼び出し前: 4181、6765。現在の番号 = 10946 引数
付きのメソッド呼び出し前: 6765、10946。現在の番号 = 17711 引数付きの
メソッド呼び出し前: 10946、17711。現在の番号 = 28657
引数付きのメソッド呼び出し前: 17711、28657。現在の番号 = 46368
引数付きのメソッド呼び出し前: 28657、46368。現在の番号 = 75025 引数付きのメソッド呼び出し前: 46368、75025。現在の
番号 = 121393 引数付きのメソッド呼び出し前
: 75025、 121393。現在の番号 = 196418
引数付きのメソッド呼び出し前: 121393、196418。現在の番号 = 317811
引数付きのメソッド呼び出し前: 196418、317811。現在の番号 = 514229 引数付きのメソッド呼び出し前
: 317811、514229。現在の番号 = 8320 40
前メソッド引数付きのメソッド呼び出し: 514229、832040。現在の番号 = 1346269
引数付きのメソッド呼び出し前: 832040、1346269。現在の番号 = 2178309 引数
付きのメソッド呼び出し前: 1346269、2178309。現在の番号 = 3524578
引数付きのメソッド呼び出し前: 2178309、3524578。現在の番号 = 5702887 引数
付きのメソッド呼び出し前: 3524578、5702887。現在の番号 = 9227465 引数付きのメソッド呼び出し前: 5702887、9227465。現在の番号
= 14930352 引数
付きのメソッド呼び出し前: 9227465、 14930352。現在の番号 = 24157817
引数付きのメソッド呼び出し前: 14930352、24157817。現在の番号 = 39088169
引数付きのメソッド呼び出し前: 24157817、39088169。現在の番号 = 63245986 引数付きのメソッド呼び出し前
: 39088169 、63245986。現在の番号 = 102334155
メソッドの前引数付きメソッド呼び出し: 63245986、102334155。現在の番号 = 165580141
引数付きメソッド呼び出し前: 102334155、165580141。現在の番号 = 267914296
引数付きのメソッド呼び出し前: 165580141、267914296。現在の番号 = 433494437
引数付きのメソッド呼び出し前: 267914296、433494437。現在の番号 = 701408733 引数付きのメソッド呼び出し前: 433494437、701408733。現在の番号
= 1134903170
引数を使用したメソッド呼び出しの前: 701408733、 1134903170。現在の番号 = 1836311903
引数付きのメソッド呼び出し後: 701408733、113490317
引数付きのメソッド呼び出し後: 433494437、701408733 引数付きのメソッド呼び出し後: 267914296、433494437 引数付き
のメソッド呼び出し後:
165580141、267914296
引数によるメソッド呼び出し後: 102334155、 165580141
引数を指定したメソッド呼び出し後: 63245986、102334155
引数を指定したメソッド呼び出し後: 39088169、63245986
引数付きのメソッド呼び出し後: 24157817、39088169
引数付きのメソッド呼び出し後: 14930352、24157817
引数付きのメソッド呼び出し後: 9227465、14930352 引数付きのメソッド呼び出し後: 5702887、9227465 引数付き
のメソッド
呼び出し後: 3524578、 5702887
引数を指定したメソッド呼び出し後: 2178309、3524578
引数付きのメソッド呼び出し後: 1346269、2178309
引数付きのメソッド呼び出し後: 832040、1346269 引数
付きのメソッド呼び出し後: 514229、832040 引数
付きのメソッド呼び出し後: 317811、514229
引数付きのメソッド呼び出し後: 196418、317811
後引数付きのメソッド呼び出し
後: 121393、196418 引数付きのメソッド呼び出し後: 75025、121393
引数付きのメソッド呼び出し後: 46368、75025
引数付きのメソッド呼び出し後: 28657、46368
引数付きのメソッド呼び出し後: 17711、28657
引数付きのメソッド呼び出し後: 10946、17711 引数
付きのメソッド呼び出し後: 6765、10946 引数付きのメソッド呼び出し後
: 4181、6765
引数付きのメソッド呼び出し後: 2584、4181
引数付きメソッド呼び出し後: 1597、2584
引数付きメソッド呼び出し後: 987、1597
引数付きメソッド呼び出し後: 610、987
引数付きメソッド呼び出し後: 377、610 引数付き
メソッド呼び出し後: 233、377
後引数付きのメソッド呼び出し後: 144、233
引数付きのメソッド呼び出し
後: 89、144 引数付きのメソッド呼び出し後: 55、89
引数付きのメソッド呼び出し後: 34、55
引数付きのメソッド呼び出し後: 21、34
引数付きメソッド呼び出し後:13、21
引数付きメソッド呼び出し後:8、13
引数付きメソッド呼び出し後:5、8
引数付きメソッド呼び出し後:3、5
引数付きメソッド呼び出し後:2、3 引数
付きメソッド呼び出し後: 1, 2
引数付きメソッド呼び出し後: 1, 1
引数付きメソッド呼び出し後: 0, 1

何が起こっているかを視覚化したものが次のとおりです。

もう一度言います。printFibonacciWithConditionメソッドが呼び出されます。現在の数値を計算します。適切な場合は、それを表示し、新しい引数を指定してprintFibonacciWithConditionメソッドを再度呼び出します。

再帰的メソッドが呼び出されている限り、これは「再帰降下」と呼ばれます。再帰的処理が終了し、メソッド呼び出しが戻ったとき、呼び出しスタックが「巻き戻されている」と言います。

再帰はプログラミングにおける興味深いトピックです。この資料をより適切に扱うために、タスクを少し変更してみましょう。新しいタスクは、 Integer.MAX_VALUEを超えないフィボナッチ数列のすべての数値を降順で出力することです。このタスクに必要なコードはすべてすでに記述されています。残っているのは、現在の番号の表示と再帰メソッドの呼び出しの順序を入れ替えることだけです。つまり、最初の例では「下降」中に計算された数値が表示されていましたが、今度は「最下位まで下降」し、「戻る途中」で数値を表示する必要があります。そしてもちろん、メインメソッドでは、再帰的メソッドを呼び出した後に表示した後、シーケンスの 2 つの最初の数値 (0 と 1) を交換します。読みやすさのために、方法。


public class Fibonacci {
    public static void main(String[] args) {
        printFibonacciWithCondition(0, 1);
        System.out.println(1);
        System.out.println(0);
    }

    private static void printFibonacciWithCondition(long penultimate, long previous) {
        long current = penultimate + previous;
        if (current > Integer.MAX_VALUE) {
            return;
        }
        printFibonacciWithCondition(previous, current);
        System.out.println(current);
    }
}
    

出力は次のようになります。

1836311903
1134903170
701408733
433494437
267914296
165580141
102334155
63245986
39088169
24157817
14930352
9227465
5702887
3524578
2178309
1346269
832040
514229
317811
196418
121393
75025
46368
28657
17711
10946
6765
4181
2584
1597
987
610
377
233
144
89
55
34
21
13
8
5
3
2
1
1
0
コメント
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION