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

小云云
小云云オリジナル
2018-03-15 15:52:021837ブラウズ

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

私は 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>

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

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

  • スタックに保存されたデータは、まさに再帰関数のパラメーターです。

  • 一般的な実装では、元の再帰関数に依存する必要があります。ループの終了条件は、まさに再帰の終了条件です。

  • 元の再帰関数を変更せずに再帰関数のパラメーターをスタックにプッシュするには、関数パラメーターを取得するために呼び出される再帰関数の代わりに関数を使用する必要があります。

  • 再帰関数の終了条件は再帰関数ごとに異なりますが、再度再帰関数が呼び出されなければ、終了条件に達したことになります。つまり、終了条件は再帰関数の呼び出しに関係します。再帰関数が呼び出されるたびに、パラメータがスタックにプッシュされます。したがって、スタックに要素があるかどうかに基づいて、終了条件に到達したかどうかを推測できます。

関連する推奨事項:

JavaScriptコールスタック、末尾再帰、手動最適化の詳細な紹介

末尾再帰に関する推奨コース

末尾再帰の使用方法の詳細な説明_PHPチュートリアル

以上がjs末尾再帰最適化コード共有の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。

声明:
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。