[Java 8](8)Lambda式による再帰の最適化(上)-末尾再帰の使用

さいきてきさいてきか
多くのアルゴリズムは再帰に依存し,典型的には分治法(Divide-and-Conquer)などである.しかし,通常の再帰アルゴリズムでは規模の大きい問題を扱う場合,StackOverflowErrorがしばしば現れる.この問題に対処するために,再帰を最適化するために,テールコール(Tail‐Call Optimization)という技術を用いることができる.また,サブ問題の結果を一時的に保存することで,サブ問題の繰返し解を回避することもでき,この最適化法をメモ(Memoization)と呼ぶ.
本文ではまず末尾再帰について紹介し,次の一票ではメモパターンについて紹介する.
末尾呼び出しによる最適化
再帰アルゴリズムが大規模な問題に適用されると,StackOverflowErrorが出現しやすくなるのは,解く必要があるサブ問題が多すぎて再帰的にネストされた階層が深すぎるためである.この場合、この問題を回避するために、テールコール最適化を採用することができる.このテクノロジーがエンドコールと呼ばれるのは、1つの再帰メソッドで最後の文が再帰コールであるからです.この点は従来の再帰法とは異なり、従来の再帰は通常、方法の中部で発生し、再帰が終了して結果を返した後、その結果に対して何らかの処理を行うことが多い.
Javaはコンパイラレベルではテール再帰技術をサポートしていません.しかし、Lambda式を用いて実現することができます.次に,この技術を乗算アルゴリズムに適用することによって再帰的な最適化を実現する.次のコードは、最適化されていない乗算再帰アルゴリズムです.

public class Factorial {
    public static int factorialRec(final int number) {
        if(number == 1)
            return number;
        else
            return number * factorialRec(number - 1);
    }
}

以上の再帰アルゴリズムは,小規模な入力を扱う場合には正常に解けるが,大規模な入力を入力するとStackOverflowErrorを放出する可能性が高い.

try {
    System.out.println(factorialRec(20000));
} catch(StackOverflowError ex) {
    System.out.println(ex);
}

// java.lang.StackOverflowError

この問題の原因は、再帰自体ではなく、再帰呼び出しの終了を待つと同時にnumber変数を保存する必要があるためです.再帰法の最後の操作は乗算操作であるため、サブ問題を解く場合(factorialRec(number - 1))、現在のnumber値を保存する必要がある.したがって、問題の規模が増加するにつれて、サブ問題の数も増加し、各サブ問題は呼び出しスタックの1層に対応し、呼び出しスタックの規模がJVM設定のしきい値より大きい場合、StackOverflowErrorが発生する.
末尾再帰に変換
最後の再帰に変換する鍵は、自身の再帰呼び出しが最後の操作であることを保証することです.上記の再帰的な方法のように、最後の操作は乗算操作ではありません.これを回避するために,乗算操作を先に行い,結果をパラメータとして再帰法に伝達することができる.しかし、再帰呼び出しが発生するたびに呼び出しスタックにスタックフレーム(Stack Frame)が作成されるため、それだけでは十分ではありません.再帰的呼び出し深度が増加すると、スタックフレームの数も増加し、最終的にはStackOverflowErrorをもたらす.スタックフレームの作成は、再帰呼び出しを遅延化することによって回避できます.次のコードはプロトタイプ実装です.

public static TailCall<Integer> factorialTailRec(
    final int factorial, final int number) {
    if (number == 1)
        return TailCalls.done(factorial);
    else
        return TailCalls.call(() -> factorialTailRec(factorial * number, number - 1));
}

パラメータfactorialは初期値であり、numberは乗算を計算する必要がある値である.再帰呼び出しはcallメソッドが受け入れるLambda式に現れることが分かった.上記のコードのTailCallインタフェースとTailCallsツールクラスはまだ実装されていません.
TailCall関数インタフェースの作成
TailCallの目的は、従来の再帰中のスタックフレームの代わりに、複数の連続した再帰呼び出しをLambda式で表すことである.したがって,UnaryOperator関数インタフェースのapply法に似た現在の再帰操作により次の再帰操作を得る必要がある.また、これらのタスクを完了する方法も必要です.
再帰が終了したかどうかを判断する最終結果が得られたトリガ再帰このようにして、TailCall関数インタフェースを設計することができます.

@FunctionalInterface
public interface TailCall<T> {
    TailCall<T> apply();
    default boolean isComplete() { return false; }
    default T result() { throw new Error("not implemented"); }
    default T invoke() {
        return Stream.iterate(this, TailCall::apply)
            .filter(TailCall::isComplete)
            .findFirst()
            .get()
            .result();
    }
}

isComplete,result,invokeメソッドは,上述した3つのタスクをそれぞれ完了した.ただし、特定のisCompleteメソッドとresultは、再帰的な中間ステップのような再帰的な動作の性質に基づいて上書きする必要があります.たとえば、isCompleteメソッドはfalseを返すことができますが、再帰的な最後のステップの場合はtrueを返す必要があります.resultメソッドの場合、再帰的な中間ステップは例外を放出することができ、再帰的な最終ステップは結果を与える必要がある.
invokeメソッドは最も重要なメソッドであり、すべての再帰動作をapplyメソッドで直列に接続し、スタックフレームのないテールコールによって最後の結果を得る.直列方式はStreamタイプが提供するiterateメソッドを利用しており、本質的に無限のリストであり、再帰呼び出しの発生数は限られているが、この数は未知であってもよいため、再帰呼び出しの特徴にある程度合致している.この無限リストに終端を描く操作がfilterとfindFirstの方法です.すべての再帰呼び出しでは、isCompleteで最後の再帰呼び出しのみがtrueを返すため、呼び出されると、再帰呼び出しチェーン全体の終了を意味します.最後にfindFirstでこの値を返します.
Streamのiterateメソッドに慣れていない場合は、前の記事を参考に、このメソッドの使用について説明します.
TailCallsツールクラスの作成
プロトタイプ設計では、TailCallsツールクラスのcallメソッドとdoneメソッドが呼び出されます.
callメソッドは、現在の再帰の次の再帰を得るために使用される.
done法は一連の再帰操作を終了するために用いられ,最終的な結果を得た.

public class TailCalls {
    public static <T> TailCall<T> call(final TailCall<T> nextCall) {
        return nextCall;
    }
    public static <T> TailCall<T> done(final T value) {
        return new TailCall<T>() {
            @Override public boolean isComplete() { return true; }
            @Override public T result() { return value; }
            @Override public TailCall<T> apply() {
                throw new Error("end of recursion");
            }
        };
    }
}

done法では,最終的な結果を表すための特別なTailCall例を返した.そのapply法は、最終的な再帰結果に対して後続の再帰動作がないため、例外を放出するように呼び出されるように実装されることに留意されたい.
以上のTailCallとTailCallsは,階乗という簡単な再帰アルゴリズムを解決するために設計されたが,いずれの末尾再帰を必要とするアルゴリズムにおいても役に立つに違いない.
末尾再帰関数の使用
これらを使用して乗算問題を解決するコードは簡単です.

System.out.println(factorialTailRec(1, 5).invoke());      // 120
System.out.println(factorialTailRec(1, 20000).invoke());  // 0

1番目のパラメータは初期値を表し、2番目のパラメータは乗算を計算する必要がある値を表します.
しかし、20000の階乗を計算する際に誤った結果が得られたのは、整数データがこのような大きな結果を収容できず、オーバーフローが発生したためである.この場合、Integerタイプの代わりにBigIntegerを使用することができる.
実際にfactorialTailRecの最初のパラメータは必要なく、一般的には初期値は1であるべきである.これにより、次のように簡単になります.

public static int factorial(final int number) {
    return factorialTailRec(1, number).invoke();
}

//     
System.out.println(factorial(5));
System.out.println(factorial(20000));

Integerの代わりにBigIntegerを使用
主にdecrementメソッドとmultipleメソッドを定義して、大規模なデータの乗算操作を支援する必要があります.

public class BigFactorial {
    public static BigInteger decrement(final BigInteger number) {
        return number.subtract(BigInteger.ONE);
    }

    public static BigInteger multiply(
        final BigInteger first, final BigInteger second) {
        return first.multiply(second);
    }

    final static BigInteger ONE = BigInteger.ONE;
    final static BigInteger FIVE = new BigInteger("5");
    final static BigInteger TWENTYK = new BigInteger("20000");
    //...

    private static TailCall<BigInteger> factorialTailRec(
        final BigInteger factorial, final BigInteger number) {
        if(number.equals(BigInteger.ONE))
            return done(factorial);
        else
            return call(() ->
                factorialTailRec(multiply(factorial, number), decrement(number)));
    }

    public static BigInteger factorial(final BigInteger number) {
        return factorialTailRec(BigInteger.ONE, number).invoke();
    }
}