トランポリン、Java の例

n から 0 までの数値を加算する簡単なプログラムを書いてみましょう。しかし、反復的なアプローチを使用する代わりに、再帰的なアプローチを試してみてはいかがでしょうか?

このプログラムを sum と呼びます。 sum(0) == 0 はわかっているので、これが基本ケースです。どのようにして基本ケースに到達するのでしょうか? sum(n) == n sum(n-1)、ついにsum(0)に至るまで。 Java コードは次のとおりです:

<code class="language-java">int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}</code>

再帰の問題?

基本ケースが入力値から遠く離れている場合、再帰には固有の欠陥があります...ほとんどの言語では、関数呼び出しはプログラムのスタックを使用して関数呼び出し情報を保存するため、非常に大規模な再帰はスタック オーバーフローを引き起こす可能性があります。

しかし、これを回避する方法はあるのでしょうか?実はあるんです。これはトランポリンと呼ばれる古い戦略です。

スプリングボード

スプリングボード戦略の基本的な考え方は、プログラムの一部が「値」または「継続」を返すというものです。継続とは何ですか？処理を継続する関数。

おおよそ次のとおりです:

<code class="language-java">let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;</code>

sumの続きは何ですか?

プログラムを次のようにモデル化してみましょうsum: 単純に再帰する代わりに、継続を使用します。 1 つの方法は、継続を介して渡されるオブジェクトとして acc を使用することです。したがって、sum_trampoline(0, acc) に到達すると、acc を返します。どのように進めればよいでしょうか?

sum_trampoline(n, acc)からsum_trampoline(n-1, acc n)に行きましょう。最初の入力は sum_trampoline(n, 0) です。

コードは次のとおりです:

<code class="language-java">Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}</code>

タイプを使用して踏み台を説明します

踏み台はおおよそ次の形式である必要があります:

<code class="language-java">let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;</code>

しかし、これによりコーディングの自由度が大幅に高まりますが、Java の世界ではあまり直感的ではありません。オブジェクトに問い合わせることで、それが継続しているかどうかを確認できます。 「値は見つかりましたか?」と尋ねるとどうなるでしょうか。もう 1 つは、Java には sum 型がないため、return trampolim は値を返すのではなく、実際には trampolim 型を返すことです。 trampolim.value()に戻ることができます。

最後に、重要なポイントは、踏み台のブートストラップです。これを行うには、関数を使用して入力を適切な pogo 戻り値に変換します。入力と結果は、より良く使用するために一般化できます:

<code class="language-java">public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}</code>

TrampolineStep<R>インターフェースについてはどうですか?

3 つのメソッドが定義されています:

• gotValue: 値が見つかったかどうかを尋ねます
• value: 見つかった値
を返します。
• runNextStep: 値または継続を返します

基本的に 2 つの状態があります:

• 値が見つかりました
• 続きです

したがって、静的メソッドを使用して初期化できます。値が見つかった場合は、その値を渡す必要があります:

<code class="language-java">int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}</code>

継続の場合、継続の次の項目を取得する方法を渡す必要があります:

<code class="language-java">let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;</code>

sum_trampolineこれはどのように達成されるのでしょうか?

<code class="language-java">Object sum_trampoline_bootstrap(int n) {
    return sum_trampoline(n, 0);
}

Object sum_trampoline(int n, int acc) {
    if (n == 0) {
        return acc;
    }
    return (Supplier<object>) () -> sum(n - 1, acc + n);
}</code>

テールコールフィボナッチ

フィボナッチの古典的な実装は再帰的定義に従います。

<code class="language-java">let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;</code>

フィボナッチ定義を再帰的ではなく前方に拡張する反復バージョンもあります: 0 と 1 から開始して、対応する値に到達するまで:

<code class="language-java">public static <R> R trampoline(IN input,
                                   Function<IN, TrampolineStep<R>> trampolinebootStrap) {
  TrampolineStep<R> nextStep = trampolinebootStrap.apply(input);
  while (!nextStep.gotValue()) {
    nextStep = nextStep.runNextStep();
  }
  return nextStep.value();
}</code>

「末尾呼び出し再帰」を使用した、この実装の前方バージョンがあります:

<code class="language-java">static <X> TrampolineStep<X> valueFound(X value) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return true;
        }

        @Override
        public X value() {
            return value;
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return this;
        }
    };
}</code>

ここでは、再帰的フィボナッチの末尾呼び出しで使用される数値を準備する入力インターフェイスを分離します。先に進むにつれて、マッピング fib[0] => 0、fib[1] => 1 から開始し、インデックス 0 からインデックス n に到達するまでナビゲートします。

フィボナッチ: テールコールからスプリングボードまで

fib_tc の例は、フィボナッチ スプリングボードをよく示しています。

<code class="language-java">static <X> TrampolineStep<X> goonStep(Supplier<TrampolineStep<X>> x) {
    return new TrampolineStep() {
        @Override
        public boolean gotValue() {
            return false;
        }

        @Override
        public X value() {
            throw new RuntimeException("dont call this");
        }

        @Override
        public TrampolineStep<X> runNextStep() {
            return x.get();
        }
    };
}</code>

これは単なるスケルトンであり、コンパイルして実行するには、TrampolineStep インターフェースの完全な実装と trampoline 関数の完全な実装が必要であることに注意してください。 さらに、IN を特定の入力タイプに置き換える必要があります。

以上がトランポリン、Java の例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。