再帰関数、スタックオーバーフロー、およびYコンビネータ

Question

約8億回呼び出す必要のある再帰関数（C＃）があります。これは明らかに通常、約900回目の呼び出し後にスタックオーバーフローを引き起こします。これを複数のループにキックアウトしましたが、再帰パターンは非常に簡単で、保守がよりクリーンです。

私が読んで見たように、y-combinatorを使用して再帰関数を実装することを検討しています。これにより、スタックオーバーフローの問題が解決され、複数のネストされたループが修正されます。

y-combinatorの使用経験はありますか？それでもスタックオーバーフローでスタックしますか？

階乗の簡単な例を見てください。5,000を超えるほとんどの数値の階乗は、スタックオーバーフローを引き起こします。そのシナリオでy-combinatorを適切に使用した場合、スタックオーバーフローは修正されますか？

実装するのは簡単ではないようです。そのため、y-combinatorの実装と学習に開発作業/リソースを費やす前に、それを確認したいと思います。

Answer 1

いいえ、Y-combinatorを使用しても状況は改善されません。8億回何かを行う必要がある場合は、（a）再帰するか、（b）ループすることができます（または（c）関数に8億回の呼び出しを書き込むと思います）。Y-combinatorはループしないため、再帰する必要があります。

適切な末尾再帰を提供するランタイム環境（Schemeなど）を使用していない限り、ループはあなたが探しているものです。

そうは言っても、選択した言語でY-combinatorを最初から実装することは優れた演習です。

Answer 2

Yコンビネータは便利ですが、末尾再帰関数にスタックを使用しないようにする末尾再帰の最適化が本当に必要だと思います。末尾再帰は、すべての再帰呼び出しの結果が呼び出し元によってすぐに返される場合にのみ可能であり、呼び出し後に追加の計算が行われることはありません。残念ながら、C＃は末尾再帰の最適化をサポートしていませんが、トランポリンでエミュレートできます。これにより、末尾再帰方式からトランポリンラップ方式への簡単な変換が可能になります。 ジェネラコディセタグプレ

Answer 3

Reactive Extensionで使用されているようにトランポリンを使用できます。ブログで説明しようとしました http://rohiton.net/2011/08/15/trampoline-and-reactive-extensions/

Answer 4

1つの解決策は、ループと明示的な context データ構造を使用するように関数を変換することです。コンテキストは、人々が一般的にコールスタックと考えるものを表します。 別の質問に対する私の答えが見つかるかもしれません末尾再帰への変換について便利です。関連する手順は1から5です。 6と7はその特定の機能に固有ですが、あなたの機能はもっと複雑に聞こえます。

ただし、「簡単な」代替手段は、各関数に深度カウンターを追加することです。 （実験によって決定された）制限に達したら、新しいスレッドを生成して、新しいスタックで再帰を続行します。古いスレッドは、新しいスレッドが結果を送信するのを待っていることをブロックします（または、空想したい場合は、結果または例外を再発生させます）。新しいスレッドの深度カウンターは0に戻ります。制限に達したら、3番目のスレッドを作成します。スレッド作成コストを必要以上に頻繁に支払わないようにスレッドをキャッシュする場合は、プログラムを大幅に再構築しなくても、許容できるパフォーマンスが得られることを願っています。