markdown

はじめに (対象読者・この記事でわかること)

この記事は、Javaで関数型プログラミングや再帰的アルゴリズムを扱う開発者、特にスタックオーバーフローを回避したい方を対象としています。
「トランポリン」と呼ばれる手法が何を意味するのか、なぜその名前が付けられたのかを歴史的・概念的に紐解きます。また、実際にJavaコードでトランポリンを実装する手順と、よくある落とし穴の対処法を具体例とともに示すので、読了後には自分のプロジェクトにすぐ適用できる知識が得られます。

前提知識

この記事を読み進める上で、以下の知識があるとスムーズです。
- Javaの基本的な文法とオブジェクト指向の概念
- 関数型インタフェース（java.util.function）およびラムダ式の基本的な使い方
- JVMのスタック構造とスタックオーバーフローの概念（初心者向けの簡単な説明は本記事で補足）

トランポリン手法の概要と命名の背景

トランポリン（英: trampoline）という名称は、「跳ね返す」というイメージから来ています。元々は関数型言語の実装において、再帰呼び出しによるスタック深さの増大を防ぐ手法として登場しました。
具体的には、再帰的な関数呼び出しを直接行うのではなく、「次に実行すべき処理」をオブジェクトとして返し、呼び出し側がループでそれを取り出して実行」する形を取ります。この「次に実行すべき処理」を「跳ね返す」イメージで捉えると、ちょうどトランポリンに乗って次々に跳び上がる様子に似ていることから名前が付けられました。

Javaの世界でも、JDK8以降に導入されたSupplierやFunctionといった関数型インタフェースを組み合わせることで、トランポリン的な実装が可能です。特に末尾再帰（Tail Recursion）を最適化できないJVMに対し、手動で「トランポリン」構造を作ることでスタックフレームの増加を抑えるテクニックとして注目されています。

この手法は、「計算の途中で次のステップを保持し、外部ループがそのステップを評価」という形になるため、「再帰的ロジックをイテレーティブに変換」することができます。結果として、深い再帰が必要なアルゴリズム（例: フィボナッチ数列の計算、木構造の深さ優先探索）でもスタックオーバーフローを回避できるようになります。

Javaでトランポリンを実装する具体的手順

以下では、実際にJavaコードを書きながらトランポリン手法を実装する流れを説明します。例として、階乗（Factorial）をトランポリンで求めるプログラムを作成します。

ステップ1：トランポリン用のインタフェースを定義する

まずは「次に実行すべき計算」を表すインタフェース Trampoline<T> を作成します。Trampoline は評価（evaluate）と次のステップ取得（bounce）の二つのメソッドを持ちます。

Java

@FunctionalInterface
public interface Trampoline<T> {
    // 現在のステップを評価し、結果が得られれば返す
    T get();

    // 次のステップがまだある場合はそれを返す
    default Trampoline<T> bounce() {
        return this;
    }

    // 完了状態かどうかを判定
    default boolean isComplete() {
        return true;
    }

    // 静的メソッドで完了状態のインスタンスを作成
    static <T> Trampoline<T> done(T result) {
        return () -> result;
    }

    // 静的メソッドで次のステップを遅延評価するインスタンスを作成
    static <T> Trampoline<T> more(Supplier<Trampoline<T>> supplier) {
        return new Trampoline<T>() {
            @Override
            public T get() {
                // 実際には呼び出さない
                throw new UnsupportedOperationException();
            }

            @Override
            public Trampoline<T> bounce() {
                return supplier.get();
            }

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

    // ループで全ステップを評価
    default T run() {
        Trampoline<T> current = this;
        while (!current.isComplete()) {
            current = current.bounce();
        }
        return current.get();
    }
}

ポイントは more メソッドで次ステップを 遅延評価 させ、run メソッドでイテレーティブに実行する点です。

ステップ2：階乗計算をトランポリンで表現する

次に、再帰的に階乗を求めるロジックを Trampoline に置き換えます。

Java

public class Factorial {
    // 再帰的にTrampolineを組み立てる
    public static Trampoline<BigInteger> factorial(int n, BigInteger acc) {
        if (n == 0) {
            return Trampoline.done(acc);
        } else {
            // 次のステップを遅延評価で返す
            return Trampoline.more(() -> factorial(n - 1, acc.multiply(BigInteger.valueOf(n))));
        }
    }

    // 呼び出し側のシンプルなAPI
    public static BigInteger factorial(int n) {
        return factorial(n, BigInteger.ONE).run();
    }

    public static void main(String[] args) {
        System.out.println("10! = " + factorial(10)); // 3628800
    }
}

factorial メソッドは 引数 acc に累積積を保持し、ベースケース (n == 0) では Trampoline.done で結果を返します。再帰呼び出しは Trampoline.more に包んで遅延させるため、スタックは増えません。run() がイテレーティブに全ステップを回すことで最終的な結果が得られます。

ステップ3：実際にスタック深さを検証する

Java

public static void main(String[] args) {
    // 100,000階乗でもスタックオーバーフローしないことを確認
    System.out.println("100000! の桁数 = " + factorial(100000).toString().length());
}

普通の再帰実装では数千回の呼び出しで StackOverflowError が発生しますが、上記トランポリン実装は ループでステップを処理 するため、メモリ許容範囲内であれば任意の深さを扱えます。

ハマった点やエラー解決

1. Supplier の遅延評価を忘れた

Trampoline.more(() -> factorial(...)) のように ラムダ式で遅延させる 必要があります。単に Trampoline.more(factorial(...)) と書くと、再帰呼び出しが即座に評価されてしまいスタックが増えてしまいます。

2. get() が未実装になるケース

Trampoline.more の匿名クラスで get() を例外送出していますが、run() が isComplete() が true になるまで bounce() のみを呼び出すため、実際に get() が呼ばれるのは done 状態だけです。これを忘れると UnsupportedOperationException がスローされます。

3. BigInteger のオーバーフロー

int 型で累積結果を保持すると桁あふれが起こります。必ず BigInteger を使用するか、計算範囲に合わせた型を選択してください。

解決策

  • 遅延評価は必ずラムダで包む：Trampoline.more(() -> ...) の形に統一する。
  • run() の実装を正しく：while (!current.isComplete()) { current = current.bounce(); } のループで完了状態になるまで繰り返す。
  • 型の選択：大きな数値が必要なら BigInteger、高速が必要なら long といったように目的に応じて型を変える。

まとめ

本記事では、Javaにおけるトランポリン手法の命名由来と実装方法を解説しました。

  • トランポリンという名称は「次の処理を跳ね返す」イメージから来ており、再帰をイテレーティブに変換する手法です。
  • Trampoline<T> インタフェースを自作し、more と done によって遅延評価と完了状態を表現します。
  • 階乗計算の例で示したように、スタック深さに依存せずに任意の再帰ロジックを安全に実行できます。

これにより、スタックオーバーフローを回避しつつ、関数型スタイルの再帰ロジックをJavaで活用できるようになります。次回は、非同期処理やストリーム API と組み合わせたトランポリンの応用について取り上げる予定です。

参考資料