Javaで実装する再帰の末尾呼び出し最適化

再帰は強力なアルゴリズムであり、様々な実装に用いられていますが、現実では間違った実装をしてしまうとメモリが枯渇してしまうことなどの問題があり、あまり好まれていないことも多いアルゴリズムだと考えています。

ですが、正しくプログラミングする方法を知っていれば、再帰を使うことのメリットを享受できるとも思っています。

フィボナッチ数列をJavaでプログラミングしながら、スタックオーバーフローが発生しない再帰のプログラムを書いてみようと思います。

よくあるフィボナッチ数列の実装

以下にフィボナッチ数列の簡単な実装をしてみました。

public class Fibonacci {
    public int fibonacci(int n) {
        if (n <= 0) {
            return 0;
        } else if(n == 1) {
            return 1;
        } else {
            return fibonacci(n - 2) + fibonacci(n - 1);
        }
    }
}

以下を実行してみようと思います。

@Test
public void test0() {
    assertThat(fibo.fibonacci(0), is(0));
}

@Test
public void test1() {
    assertThat(fibo.fibonacci(1), is(1));
}

@Test
public void test5() {
    assertThat(fibo.fibonacci(5), is(5));
}

上記の３つのケースは全て成功します。

ここまでであれば、最初のフィボナッチ数列の実装は問題が無いように思えますが、以下のコードでは問題が発生します。

@Test
public void test10000() {
    // 結果は間違っていますが無視してください。
    assertThat(fibo.fibonacci(100000), is(100000));
}

筆者の環境ではStackOverflowErrorが発生しました。
よって、上記のフィボナッチ数列の実装では大きな数値を扱うことができないことがわかりました。

上記のfibonacci()の再帰で書かれているコードの行で最後に実行されているのは、+演算子です。
そのため、再帰の部分の計算結果は保持され続けます。
その間、再帰呼出しの部分をコールスタックに積み上げ続けます。
そのため、再帰の実行回数が多くなると、コードが失敗してしまいます。

このような問題が発生するようなコードは、実際の環境では扱うことが難しいと思います。

末尾再帰とは

修正したコードを見る前に、末尾再帰について確認しておこうと思います。

再帰的な関数において、自身の再帰呼出しが処理の最後のステップになっているような再帰のパターンのことをさします。
関数のreturnの部分がreturnと関数呼び出しのみで構成されている必要があります。

また、再帰にかかわらず、関数の最後の処理を呼び出すことを末尾呼び出しといいます。

また、末尾呼出しのコードを、戻り先を保存しないジャンプに変換することによって、スタックの累積を無くす機能のことを、末尾呼び出し最適化といいます。
HaskellやSchemeなどの関数型言語の多くは、末尾再帰を最適化する機能が言語レベルでサポートされています。
ですが、Javaでは言語レベルではサポートされていません。

末尾呼び出し最適化されたフィボナッチ数列

これを解決するためには、スタックに積み上げず実行するようにコードを変更する必要があります。

Javaによる関数型プログラミングを参考に、コードを書きました。

public class Fibonacci2 {

    @Autowired
    TailCallUtil tailCallUtil;

    public BigInteger fibonacci(int n) {
        return this.fibonacciTailCall(BigInteger.valueOf(n), ONE, ZERO).call();
    }

    public TailCall<BigInteger> fibonacciTailCall(BigInteger n1, BigInteger n2, BigInteger n3) {
        System.out.println("called");
        if (n1.compareTo(ZERO) <= 0) {
            return tailCallUtil.complete(ZERO);
        } else if (n1.compareTo(ONE) == 0) {
            return tailCallUtil.complete(n2);
        }
        return tailCallUtil.nextCall(() -> fibonacciTailCall(n1.subtract(ONE), n2.add(n3), n2));
    }
}

呼び出し方は最初のコードと同じです。

@Test
public void test5() {
    assertThat(fibo.fibonacci(5), is(BigInteger.valueOf(5)));
}

新たにfinobacciTailCall()を作成し、末尾再帰の関数としました。
また、フィボナッチ数列の計算結果は大きな値になりやすいため、finobacciTailCall()の引数はjava.math.BigIntegerに変更しました。

次に、TailCall.javaとTailCallUtil.javaを見てみようと思います。

@FunctionalInterface
public interface TailCall<T> {

    TailCall<T> apply();

    default boolean isComplete() {
        return false;
    }

    default T getResult() {
        throw new RuntimeException("Not implemented.");
    }

    default T call() {
        return Stream.iterate(this, TailCall::apply)
                .filter(TailCall::isComplete)
                .findFirst()
                .orElseThrow(() -> new RuntimeException("Unreachable"))
                .getResult();
    }
}

@Component
public class TailCallUtil {

    public <T> TailCall<T> nextCall(TailCall<T> function) {
        return function;
    }

    public <T> TailCall<T> complete(T value) {
        return new TailCall<T>() {
            @Override
            public TailCall<T> apply() {
                throw new RuntimeException("Not implemented.");
            }

            @Override
            public boolean isComplete() {
                return true;
            }

            @Override
            public T getResult() {
                return value;
            }
        };
    }
}

この２つのクラスとインターフェースを使うことにより、スタックに積み上げないように実行することが可能になります。
実際の処理の流れですが、
1. Fibonacci#fibonacciTailCallが1度だけ実行され、TailCall.javaのインスタンスを返す
2. TailCall#callが呼ばれると、Stream.iterateから渡した関数(Fibonacci#fibonacciTailCall)が呼ばれる。これは再帰呼出し分実行される。
3. いずれTailCallUtil#completeが実行される。そうすると再帰呼び出しは終了される。
4. TailCall#getResultの値が返却される。

再帰呼び出しの部分は遅延して実行されます。よって、再帰の呼び出し部分をコールスタックに積み上げ続けることなく実行されます。

以下のような大きな入力値でも、問題なく実行できます。

@Test
public void test30000() throws Exception {
// 検証値は実際は100行以上ありますが、省略します
    assertThat(fibo.fibonacci(30000), is(new BigInteger(""
                + "19042435673462438748500976847175750289440229160233"
                + "35192733911840520448018633401564505514339826149631" ....
     )));
}

まとめ

再帰は正しくプログラミングすることができれば、使うことにメリットがあるケースも多くあるのではないかと考えています。
ですが、逆に言うと正しいプログラミングができないと、予期しない不具合を仕込んでしまいやすいアルゴリズムだとも思います。
そして、正しく使用するためには、末尾再帰への理解は不可欠だと思います。
Javaは言語レベルでは末尾呼び出し最適化をサポートしていませんが、Javaの標準ライブラリを利用して、数十行のコードで利用することができます。
なので、再帰を毛嫌いせずに、有効利用できる場面では使っていこうと思います。

参考

Javaによる関数型プログラミング ―Java 8ラムダ式とStream
https://ja.wikipedia.org/wiki/%E6%9C%AB%E5%B0%BE%E5%86%8D%E5%B8%B0

以下にソースコードを公開しました。
https://github.com/ftsan/tailCallOptimization

Javaによる関数型プログラミング ―Java 8ラムダ式とStream　　
末尾再帰 - Wikipedia