問題タブ [tail-recursion]

前の質問で、末尾再帰を使用するように計算式を書き直す方法を説明しました。コードを書き直しましたが、StackOverflowExceptionが発生しました。問題を特定するために、状態モナド（このブログエントリから取得）を使用していくつかの小さなコードを記述しました。

Loop関数は末尾再帰（？）を使用できますが、これによりStackOverflowExceptionが再びスローされます。StateBuilderクラスに何か問題があると思います。私はDelayメソッドで何かをしようとしました。すべてを余分なラムダでラップしますが、成功しません。私は現時点で完全に立ち往生しています。ここで私の2番目の試み（コンパイルされません）：

私は部屋を作る工場を作っています、そしてそれはステップのintとスタートルームを通過し、そしてそれはステップを実行し、部屋を作り、そしてそれから一歩少ないステップでそれ自身を呼び、そして新しい部屋をスタートルームとして呼ぶことになっています。問題はそれが決して終わらないということです。デバッガーでは、それ自体が呼び出していることがわかります。これにより、実際にはステップが1つ少ない別のメソッド呼び出しがメモリ内に作成されますが、実行行は現在のメソッド呼び出しの先頭に移動します。したがって、実際に新しい呼び出しが完了することはありません。新しい呼び出しをスタックではなくヒープに入れて、実際に到達することはないかのように。

コード：

上記のコードでは、さまざまな実装を経て、place（）の新しい呼び出しに到達し、place（）の新しいインスタンスを作成するだけですが、それにステップインせず、代わりに実行行が移動します元の呼び出しの「Roomroom=start_room」に戻ります。これは無限に行われ、サイクルは常に初期値の4であり、place（）のインスタンスがスタックを埋め尽くします。新しいインスタンスを調べましたが、実際にはすべてのインスタンスの「サイクル」値は3です。

奇妙なことに、実際に実行される各反復は次の部屋で実行されているため、トップに戻ると、次の部屋を通過してトップに戻ります。しかし、なぜそれはplace（）の新しいインスタンスを作成し（新しい部屋と新しいサイクル値3で）、新しい部屋を使用して古いplace（）を再実行しますが、新しいサイクル値3ではないのですか？

私は F# が初めてで、末尾再帰関数について読んでいて、誰かが関数 foo の 2 つの異なる実装を教えてくれることを望んでいました。

この F# seq 式は末尾再帰のように見えますが、スタック オーバーフロー例外が発生しています (末尾呼び出しが有効になっている場合)。私が欠けているものを誰か知っていますか？

ご参考までに、重要ではありませんが、pickはシーケンス内の要素の組み合わせを生成するために使用されinterleave、2 つのシーケンスから要素をインターリーブします。vectorのコンストラクタですResizeArray。

私の記憶が正しければ、末尾再帰関数には常に簡単な非再帰関数があります。再帰には不要な関数呼び出しのオーバーヘッドが伴うため、非再帰的な方法で実行することをお勧めします。

この仮定は常に正しいですか？末尾再帰に賛成/反対する他の議論はありますか?

私はfoldlとfoldrをテストしたかった。私が見てきたことから、末尾再帰の最適化のために、可能な限りfoldrよりもfoldlを使用する必要があります。

意味あり。ただし、このテストを実行した後、私は混乱しています：

folderr (time コマンドを使用する場合は 0.057 秒かかります):

foldl (time コマンドを使用すると 0.089 秒かかります):

この例が些細なことであることは明らかですが、foldr が foldl を上回っている理由については混乱しています。これは、foldl が勝つ明確なケースではないでしょうか?

Clojureについて質問があります。ProjectEulerを使用して言語を学習しようとしていますが、内部で何が起こっているのかわかりません。次のコードは、までのすべての素数のリストを返すように設計されていますlim。limまでのすべての数値のリストを作成し、最初の数値を新しいリストに移動しながら1つずつフィルターで除外するため、ヒープスペースではO（n）である必要があると思います。（私は実際に毎回新しいリストを作成していることを知っていますが、それらがより多くのメモリを必要とするとは思いませんでしたか？）とにかく私はこれを実行しています

そして、電話をかけると、ヒープスペースが不足し続けます

、しかし私は上のスペースを使い果たしていません

したがって、リストがrecurの呼び出しでガベージコレクションされ、実際にO（n * n）ヒープなどを使用していることを理解してはいけないと思います。

どうにかしてメモ化と末尾再帰を組み合わせることができますか? 私は現在 F# を学んでおり、両方の概念を理解していますが、それらを組み合わせることができないようです。

次のmemoize関数があるとします ( Real-World Functional Programmingから):

および次のfactorial関数:

メモ化factorialはそれほど難しくなく、末尾再帰にすることも難しくありません。

しかし、メモ化と末尾再帰を組み合わせることができますか? 私はいくつかの試みをしましたが、うまくいかないようです。それとも、これは単に不可能ですか？

シーケンスの最初の要素をリストに再帰的に追加することにより、シーケンスからリストを構築しようとしています:

2 つの問題:

. スタック オーバーフローが発生しました。これは、テール リカッシブな策略がひどい

と

. |> Seq.cacheここ に置くと、コードが 100 倍高速になるのはなぜですかlet newS = s |> Seq.skip(1)|> Seq.cache。

(これはほんの少しの演習であることに注意してください。Seq.toList などを実行できることは理解しています。)

どうもありがとう

機能する1つの方法は次のとおりです（2つのポイントはまだ私には少し奇妙です）：

Cは末尾呼び出しの除去を実行しないとよく言われます。規格では保証されていませんが、とにかくまともな実装で実際に実行されているのではないでしょうか。成熟した、適切に実装されたコンパイラのみを対象とし、あいまいなプラットフォーム用に作成されたプリミティブコンパイラへの絶対的な最大移植性を気にしないと仮定すると、Cで末尾呼び出しの削除に依存するのは合理的ですか？

また、末尾呼び出しの最適化を標準から除外する理由は何でしたか？