はじめに

最近, 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 {
}

所感

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

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