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

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

再帰的問題をもう一度見てみましょう。例として、フィボナッチ数の計算を考えてみましょう。フィボナッチ数列は、最初の 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 のメソッド呼び出しスタックが何であるかを思い出してください。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);
        }
    }
}
    

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

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

もう一度言います。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);
    }
}
    

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