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

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

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

再帰の問題?

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

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

スプリングボード

スプリングボード戦略の基本的な考え方は、プログラムの一部が「?jìng)帯工蓼郡稀妇@続」を返すというものです。継続とは何ですか？処理を継続する関數(shù)。

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

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

sumの続きは何ですか?

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

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

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

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);
}

タイプを使用して踏み臺(tái)を説明します

踏み臺(tái)はおおよそ次の形式である必要があります:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

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

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

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();
}

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

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

• gotValue: 値が見つかったかどうかを?qū)い亭蓼?
• value: 見つかった値
を返します。
• runNextStep: 値または継続を返します

基本的に 2 つの狀態(tài)があります:

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

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

int sum(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sum(n - 1);
}

継続の場(chǎng)合、継続の次の項(xiàng)目を取得する方法を渡す必要があります:

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

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

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);
}

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

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

let trampolim = primeiraChamada(input);

while (trampolim is continuation) {
    trampolim = trampolim.continue();
}
return trampolim;

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

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();
}

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

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;
        }
    };
}

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

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

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

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();
        }
    };
}

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

以上がトランポリン、Java の例の詳細(xì)內(nèi)容です。詳細(xì)については、PHP 中國(guó)語(yǔ) Web サイトの他の関連記事を參照してください。