問題タブ [tail-recursion]

次の関数では、アキュムレータを使用して末尾再帰を設定しようとしました。ただし、スタックオーバーフローの例外が発生しているため、関数を設定する方法で末尾再帰が正しく有効になっていないと思われます。

accを使用すると、各パスの結果をaccに詰め込み、各フレームから返すことができるため、コンパイラは、再帰呼び出しごとにすべてのスタックフレームを保持する必要がないことを確認できると理解しています。コンパイラが末尾呼び出しを行うように、アキュムレータ値を正しく使用する方法について私が理解していないことが明らかにあります。

これは、実際には F# のProject Euler Problem 14のソリューションです。ただし、より大きな数値の反復シーケンスを計算しようとすると、System.OutOfMemory 例外が発生します。ご覧のとおり、テール コールを使用して再帰関数を記述しています。

ビジュアルスタジオでデバッグしていたため（テールコールが無効になっているため）、StackOverFlowExceptionで問題が発生していました。別の質問でそれを文書化しました。ここでは、リリース モードで実行していますが、これをコンソール アプリとして実行すると、メモリ不足の例外が発生します (Windows XP 上で 4 GB RAM を使用)。

このメモリオーバーフローに自分自身をどのようにコーディングしたかを理解するのに本当に途方に暮れており、誰かが私の方法でエラーを示してくれることを望んでいます。

編集

回答による提案を考慮して、遅延リストを使用し、Int64 を使用するように書き直しました。

問題を解決します。ただし、より優れたYin Zhuのソリューションも検討します。

直接再帰を使用して配列内の左端、最下位、負の整数のインデックスを見つける関数を要求する宿題がありました。追加の要件は、関数のパラメーターが配列とサイズであり、有効な値がない場合の戻り値が-999であることでした。

私はこれを思いついた：

それは機能し、要件を満たし、私に完全な信用を得ました。これは末尾再帰で実装できますか？

再帰呼び出しの結果を比較に使用して、それを渡すか更新するかを決定する必要があるので、それは不可能だと思いますが、再帰はまだ私の脳を結びつけています。私が行方不明になっていることは明らかなことかもしれません。

注：私の宿題はすでに提出され、採点されています。

同じClojure関数でrecur機能とpost-condition機能の両方を使用することは可能ですか？事後条件を使用して例外をスローすることを望んでいましたが、Clojureは何らかの理由で再発後に例外スローコードをラップしようとしているようであるため、（ばかげた例として）このような関数は評価できません。

現在、Clojure1.3を使用しています。

これが前方再帰である理由がわかりません。

それは模擬試験の質問であり、答えはその前方再帰です。なぜそうなのですか？どうすれば2つを区別できますか？

基本的なフォームが次のようなScheme関数があります

これは明らかに、コンパイルの繰り返しに合わせて最適化する必要があるもののように感じますが、(チキンを使用して) コンパイルすると、それでも信じられないほど遅く実行されます。(R5RS の仕様を理解している場合: http://groups.csail.mit.edu/mac/ftpdir/scheme-reports/r5rs-html.old/r5rs_22.html、これは動作するはずです)

Python で while ループを使用してまったく同じアルゴリズムを作成し、解釈されたプログラムは数秒で終了しました。コンパイルされたスキームには約 15 分かかりますが、アルゴリズムは同じであると確信しています。

他に何が考えられるのか考えられないので、これは最適化されていない末尾再帰の問題だと思いますが、それを理解することはできません。何か案は？var はハッシュであり、破壊的な更新は単に要素を追加するだけですが、newvar として渡される更新されたハッシュも返します。

Haskell で書くと、

GHCでコンパイルすると、結果は私が使用した場合とは異なりますか

私は簡単にすべてを実行fac n = product [1..n]して回避することができましたが、末尾再帰の試みが怠惰な言語でどのように機能するかに興味があります。サンクが蓄積されているため、スタック オーバーフローが発生する可能性があることはわかりましたが、アキュムレータを使用した場合と単純な再帰を述べた場合では、(コンパイルされたプログラムの結果に関して) 実際には何か違うことが起こりますか? 読みやすさの向上以外に、末尾再帰を除外する利点はありますか? runhaskell最初にコンパイルするのではなく、計算を実行するために使用している場合、答えはまったく変わりますか?

私は次の制御構造を使用しています（これは末尾再帰だと思います）

反復深化を行うには

この空きメモリは（技術的には到達できなくなるため）、各反復深化後のようになりますか？そうでない場合は、制御構造をどのように書き直す必要がありますか？

PS 2番目に、末尾再帰構造は、この場合ではなくても、前の値に追加するようにスタック上のものにアクセスできることが多いため、これは失敗するように見えます。– Roman A.Taycher11月28日12:33PPS3番目に、dfsWithMaxDepthが返されるとすぐに、dfsWithMaxDepth内の値を破棄できると思いますが、多くの回答は多くのメモリを消費しません。–ローマンA.タイチャー11月2日

Rich Hickey らは、Clojure がinvokeDynamicJVM 7 または 8 で予定されている次のバージョンから大幅に改善されることはないと述べていますが、末尾再帰によるパフォーマンスの向上は見られるでしょう。

末尾再帰は影響しますか

また

コンパイラはおそらくすでにループ構造を生成しているので、これ以上速くなるとは思いません。

重複の可能性：
JVMがまだ末尾呼び出しの最適化をサポートしていないのはなぜですか？

私はオンラインで非常に多くの異なる答えを見るので、私は専門家に尋ねると思いました。