Java再帰
Java再帰
再帰は、関数呼び出し自体を作成する手法です。この手法は、複雑な問題を解決しやすい単純な問題に分解する方法を提供します。
再帰は少し理解しにくいかもしれません。それがどのように機能するかを理解するための最良の方法は、それを実験することです。
再帰の例
2つの数値を足し合わせるのは簡単ですが、数値の範囲を足すのはもっと複雑です。次の例では、再帰を使用して、2つの数値を加算するという単純なタスクに分解することにより、数値の範囲を加算します。
例
再帰を使用して、10までのすべての数値を追加します。
public class Main { public static void main(String[] args) { int result = sum(10); System.out.println(result);
}public static int sum(int k) { if (k > 0) { return k + sum(k - 1); } else { return 0;
}}
}
例の説明
sum()
関数が呼び出されると、より小さいすべての数値の合計にパラメーターが追加されk
、k
結果が返されます。kが0になると、関数は0を返します。実行中、プログラムは次の手順に従います。
10 + sum(9)
10 +(9 + sum(8))
10 +(9 +(8 + sum(7)))
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
10 +(9 + sum(8))
10 +(9 +(8 + sum(7)))
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
が0の場合、関数はそれ自体を呼び出さないためk
、プログラムはそこで停止し、結果を返します。
停止状態
ループが無限ループの問題に遭遇する可能性があるのと同様に、再帰関数は無限再帰の問題に遭遇する可能性があります。無限再帰とは、関数がそれ自体の呼び出しを停止しない場合です。すべての再帰関数には停止条件が必要です。これは、関数がそれ自体の呼び出しを停止する条件です。前の例では、停止条件はパラメーターk
が0になったときです。
概念をよりよく理解するには、さまざまな例を見ると役立ちます。この例では、関数は開始と終了の間に数値の範囲を追加します。この再帰関数の停止条件は、endがstartより大きくない場合です。
例
再帰を使用して、5から10までのすべての数値を追加します。
public class Main { public static void main(String[] args) { int result = sum(5, 10); System.out.println(result);
}public static int sum(int start, int end) { if (end > start) { return end + sum(start, end - 1); } else { return end; } } }