• このエントリーをはてなブックマークに追加

スポンサードリンク

はじめに

最近, haskell の勉強をしている関係上, Java でも再帰が使いたい.

しかし, Java で 再帰処理を書くと, いつか必ず StackOverflowError がでて プログラムが強制終了してしまう.

回避方法がないものか, 調べてみた.

検証

コード

public class RecursiveSample {
	public static void main (String args[]) {
		recursiveProcedure (1);
	}
	
	static void recursiveProcedure (int i) {
		try {
			System.out.println (i);
			recursiveProcedure (i+1);
		}
		catch (Throwable e) {
      System.out.println ("Error " + e.getMessage ());
      e.printStackTrace ();
		}
	}
}

実行結果

9917
9918
9919Error null
java.lang.StackOverflowError
at java.util.concurrent.locks.AbstractOwnableSynchronizer.<init>(AbstractOwnableSynchronizer.java:59)
at java.util.concurrent.locks.AbstractQueuedSynchronizer.<init>(AbstractQueuedSynchronizer.java:299)
at java.util.concurrent.locks.ReentrantLock$Sync.<init>(ReentrantLock.java:119)
at java.util.concurrent.locks.ReentrantLock$NonfairSync.<init>(ReentrantLock.java:203)
at java.util.concurrent.locks.ReentrantLock.<init>(ReentrantLock.java:262)
at java.util.concurrent.ConcurrentHashMap$Segment.<init>(ConcurrentHashMap.java:425)
at java.util.concurrent.ConcurrentHashMap.ensureSegment (ConcurrentHashMap.java:749)
at java.util.concurrent.ConcurrentHashMap.putIfAbsent (ConcurrentHashMap.java:1149)
at java.lang.ClassLoader.getClassLoadingLock (ClassLoader.java:464)
at java.lang.ClassLoader.loadClass (ClassLoader.java:405)
at java.lang.ClassLoader.loadClass (ClassLoader.java:412)
at sun.misc.Launcher$AppClassLoader.loadClass (Launcher.java:308)
at java.lang.ClassLoader.loadClass (ClassLoader.java:358)
at RecursiveSample.recursiveProcedure (RecursiveSample.java:9)
at RecursiveSample.recursiveProcedure (RecursiveSample.java:9)
at RecursiveSample.recursiveProcedure (RecursiveSample.java:9)

所感

あちゃー.

再帰階層に上限をつけてみる

問題は, 深すぎる再帰呼び出しにある. ある程度深くなったら, 一旦関数呼び出しから戻って, 再会してみる.

コード

public class RecursiveSample {
static int recursiveMax;
static int recursiveCount;

public static void main (String args[]) {

try {
while (true) {
recursiveMax += 10000;
recursiveCount = recursiveProcedure2 (recursiveCount);
}
} catch (RecursiveEnd e) {
System.out.println (“End”);
}

}

static int recursiveProcedure2 (int recursiveCount) throws RecursiveEnd {
if (recursiveCount == 50000) throw new RecursiveEnd ();

if (recursiveCount < recursiveMax) { System.out.println (recursiveCount); return recursiveProcedure2 (recursiveCount+1); } else { return recursiveCount; } } } class RecursiveEnd extends Exception { } [/sourcecode]

所感

loop を結局つかっていて, かっこわるい… でも一応再帰も使えている.

終了条件にマッチしたら例外を発生させて, コンテキストから飛び出すところがミソ.