再帰呼び出し
再帰呼び出しとは、自分自身を呼び続ける手法であり、多くのアルゴリズムで基本となる考え方である。
簡単な再帰呼び出しを書いてみると以下の通り。
private static void _recursive(int i) { System.out.println(i++); _recursive(i); return; } public static void main(String[] args) { _recursive(0); return; }
_recursive() メソッドは int 型の整数を引数に受け取り、それをインクリメントした値を引数にしてを再度 _recursive() メソッドを呼び出している。
実行すると、main() メソッドから最初の _recursive() メソッド呼び出しが発生した後、標準出力に1ずつ加算された値が表示される。
但し、システムリソースの制約上、再帰呼び出しは永遠に続くわけではない。
放っておくとスタックを消費し尽くし、スタックオーバフローが発生する。
Exception in thread "main" java.lang.StackOverflowError at sun.nio.cs.ext.DoubleByteEncoder.encodeArrayLoop(Unknown Source) at sun.nio.cs.ext.DoubleByteEncoder.encodeLoop(Unknown Source) at java.nio.charset.CharsetEncoder.encode(Unknown Source) at sun.nio.cs.StreamEncoder.implWrite(Unknown Source) at sun.nio.cs.StreamEncoder.write(Unknown Source) at java.io.OutputStreamWriter.write(Unknown Source) at java.io.BufferedWriter.flushBuffer(Unknown Source) at java.io.PrintStream.write(Unknown Source) at java.io.PrintStream.print(Unknown Source) at java.io.PrintStream.println(Unknown Source) at knowledgefort.labo.recursive.StackOverFlowTest._recursive(StackOverFlowTest.java:29) ・・・
スタックオーバフローを回避するには、呼び出し回数をカウントし、規定の呼び出し数を上回った場合は処理を中断するような仕掛けにしておけばよい。
private static void _recursive(int i) { count++; // 以下の行を追加。 if (count > 1000) return; System.out.println(i++); _recursive(i); return; } public static void main(String[] args) { _recursive(0); } private static int count;