js末尾再帰最適化コード共有-jsチュートリアル-php.cn

js末尾再帰最適化コード共有

小云云

リリース： 2018-03-15 15:52:02

オリジナル

1810 人が閲覧しました

データ構造とアルゴリズムを学習するとき、すべての再帰がスタック + ループに最適化できることは誰もが知っています。特定の再帰関数については、通常、手動で最適化します。

私は scala を学んでいたときに、末尾再帰の概念に出会いました。再帰を末尾再帰として記述している限り、コンパイラは自動的に最適化を支援します。
追記: すべての再帰を末尾再帰として書き換えることができるわけではありません
js では、末尾再帰は通常インタープリタによって最適化されます。ただし、すべての JavaScript インタープリターが末尾再帰最適化をサポートしているわけではありません。
末尾再帰の最適化をサポートしていない環境の場合は、スタック + ループへの再帰を手動で最適化する必要があります。
ここでは、スタック + ループへの末尾再帰を最適化するための一般的なメソッドが実装されています。
コードは、Ruan Yifeng の書籍「ECMAScript 入門」から抜粋したものです。
具体的なコードは以下の通りです

<span style="font-family: 微软雅黑, "Microsoft YaHei";">function tco(f) {<br/>    var value;    var active = false;    var accumulated = [];    return function accumulator() {<br/>        accumulated.push(arguments);        if(!active) {<br/>            active = true;            while(accumulated.length) {<br/>                value = f.apply(this, accumulated.shift());<br/>            }<br/>            active = false;            return value;<br/>        }<br/>    };<br/>}var sum = tco(function(x, y) {<br/>    if(y > 0) {        return sum(x + 1, y - 1);<br/>    } else {        return x;<br/>    }<br/>});let res = sum(1, 5)<br/>console.info(res);<br/></span>

ログイン後にコピー

このコードは非常に微妙です！

分析
あらゆる再帰はループ + スタックとして記述できることが知られています。
末尾再帰関数ごとに実装バージョンを作成せずに、末尾再帰をループ + スタック実行に変換するというアイデアを実装します。
問題は、末尾再帰的な汎用実装にあります。特定の再帰関数をターゲットにするのではなく。
重要なポイント:

スタックに保存されたデータは、まさに再帰関数のパラメーターです。
一般的な実装では、元の再帰関数に依存する必要があります。ループの終了条件は、まさに再帰の終了条件です。
元の再帰関数を変更せずに再帰関数のパラメーターをスタックにプッシュするには、関数パラメーターを取得するために呼び出される再帰関数の代わりに関数を使用する必要があります。
再帰関数の終了条件は再帰関数ごとに異なりますが、再度再帰関数が呼び出されなければ、終了条件に達したことになります。つまり、終了条件は再帰関数の呼び出しに関係します。再帰関数が呼び出されるたびに、パラメータがスタックにプッシュされます。したがって、スタックに要素があるかどうかに基づいて、終了条件に到達したかどうかを推測できます。