問題タブ [trampolines]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
javascript - トランポリンの再帰により、「最大コールスタックサイズを超えました」
私はブロックチェーンを研究しており、非常に単純な「作業証明」を実装しています。
作業証明:
トランポリン：
関数をトランポリンしても、「最大コールスタックサイズを超えました」というエラーが引き続き表示されmineます。
StackOverflow に関する他の多くの質問やさまざまなブログの記事を読みましたが、それらの多くは、トランポリンまたは TCE が問題を解決する「階乗」または「フィボナッチ」の例にのみ焦点を当てていますが、そうではありません。
私は Node 10 で作業しているので、これがブラウザーで機能しなくてもかまいません。
recursion - Groovy の trampoline() は再帰実行を大幅に遅くします - なぜですか?
私は再帰を試しています：
このように使用すると、次のようになります。
691ミリ秒で完了
行番号 2 のコメントを外し、行番号 3 ～ 4 のコメントを削除trampoline()して実行すると、数値が大幅に低くなります。
335ミリ秒で完了
したがって、トランポリンを使用すると、再帰の動作が 2 倍遅くなります。
私は何が欠けていますか？
PS
Scala 2.12 で同じ例を実行すると、次のようになります。
それは少し速く実行されます:
178ミリ秒で完了
アップデート
アノテーションを使用してクロージャーをメソッドに書き換えます。
与える
164ミリ秒で完了
そしてスーパーコールです。それにもかかわらず、私はまだ知りたいですtrampoline():)
javascript - トランポリンを継続パススタイルに適応させるには?
以下は、右折りの単純な実装です。
これは非末尾再帰であるため、トランポリンを適用できません。1 つのアプローチは、アルゴリズムを反復させ、スタックを使用して関数呼び出しスタックを模倣することです。
別のアプローチは、再帰を CPS に変換することです。
非常に遅いため、これはまだ単純です。メモリ消費量の少ないバージョンを次に示します。
再帰呼び出しは末尾の位置にあるため、選択したトランポリンを適用できるはずです。
これは機能しません。トランポリン呼び出しが継続内にあり、遅延評価されるためです。トランポリンを CPS で動作させるには、どのように適合させる必要がありますか?