問題タブ [tail-recursion]

アルゴリズムの本を読んだところ、アッカーマン関数を末尾再帰にすることはできません（彼らが言うのは「反復に変換できない」ということです）。私はこれについてかなり困惑しているので、これを試してみました：

（それはOCaml / F＃コードです）。

私の問題は、これが実際に末尾再帰であるかどうかわからないということです。確認してもらえますか？そうでない場合、なぜですか？そして最終的に、アッカーマン関数は原始再帰ではないと人々が言うとき、それはどういう意味ですか？

ありがとう！

私が正しく理解していれば、scala.util.control.TailCallsを使用して、トランポリンを使用することにより、非末尾再帰関数のスタックオーバーフローを回避できます。APIで与えられた例は簡単です：

ただし、より興味深いケースは、recursve呼び出しの後にいくつかの操作を実行する場合です。私はどういうわけかによって実行されている「ナイーブな」階乗の実装を得ました

しかし、これはひどいように見え、これが意図された使用法であるとは思えません。だから私の質問は、TailCallsを使用して階乗関数またはフィボナッチ関数を正しく作成する方法です（はい、アキュムレータを使用して末尾再帰を取得する方法を知っています）？または、TailCallsはこの種の問題には適していませんか？

私はStackOverflowExceptionこのJavaメソッドを取得します：

私は末尾呼び出しの再帰で遊んでいるので、JVMがスタックを正しく短絡しないとこれが起こると思いますか？

別の SO question への回答を作成しているときに、Mathematica の末尾再帰に関する奇妙な動作に遭遇しました。

Mathematicaのドキュメントには、末尾呼び出しの最適化が実行される可能性があることが示唆されています。しかし、私自身の実験では相反する結果が得られます。たとえば、次の 2 つの表現を対比してください。最初の例では、おそらくスタックの枯渇が原因で、7.0.1 カーネルがクラッシュします。

2 番目の実行は完了するまで実行され、意味のある結果を返すためにテール コールの最適化を利用しているように見えます。

どちらの式も末尾再帰関数を定義していますf。最初の関数の場合，Mathematica は明らかに複合文の存在を考慮して，テールコールの最適化の可能性を無効にします．$RecursionLimitまた、最初の式は によって、2 番目の式は --によって管理されていることに注意してください。これ$IterationLimitは、 Mathematica が 2 つの式を異なる方法で扱っていることを示しています。（注：上記のSOの回答には、テールコールの最適化をうまく活用するあまり工夫されていない機能があります）。

そこで質問です: Mathematica が再帰関数の末尾呼び出し最適化を実行する状況を知っている人はいますか? Mathematica のドキュメントまたはその他のWRI資料の決定的なステートメントへの参照が理想的です。憶測も大歓迎です。

私は C++ で末尾再帰関数をいじっていましたが、g++ コンパイラで少し問題が発生しました。

numbers[]次のコードでは、サイズが数百の整数を超えるとスタック オーバーフローが発生します。以下の g++ によって生成されたアセンブリ コードを調べると、twoSum_Helper がcallそれ自体に対して再帰命令を実行していることがわかります。

問題は、次のうちどれがこれを引き起こしているかです。

• 私が見落としている以下の間違いは、末尾再帰を妨げています。
• 私のg ++​​の使い方の間違い。
• g++ コンパイラ内の末尾再帰関数の検出に問題があります。

g++ -O3 -Wall -fno-stack-protector test.cg++ 4.5.0 を使用して MinGW 経由で Wi​​ndows Vista x64 でコンパイルしています。

と呼ばれるJava抽象クラスと、と呼ばれるImmutableEntityクラスレベルのアノテーションを含むいくつかのサブクラスがあります@DBTable。末尾再帰のScalaメソッドを使用して、クラス階層でアノテーションを検索しようとしています。

このコードをコンパイルすると、「@tailrec注釈付きメソッドを最適化できませんでした。異なる型の引数で再帰的に呼び出されます」というエラーが発生します。私の内側の方法の何が問題になっていますか？

ありがとう。

andステートメントで再帰呼び出しを使用して反復プロセスを構築できますか?

たとえば、目的、foo何もしない関数があります。どのようなプロセス (反復または再帰) を作成しますか?

特定の「因数分解可能な」プロパティを持つ数値を計算する次の Clojure コードがあります。（コードが正確に何をするかは二次的なものです）。

現在、私は TCO に夢中になっており、recurキーワードを使用して明示的に指示された場合にのみ、Clojure が末尾再帰を提供できることに気付きました。だから私はそれを行うためにコードを書き直しました（唯一の違いはrecurでfactor-9を置き換えます）：

私の知る限り、TCO には 2 つのメリットがあります。最初のものは、非末尾再帰呼び出しほどスタックを使用しないため、より大きな再帰でスタックを吹き飛ばさないことです。2つ目は、ループに変換できるため、結果として高速になると思います。

さて、私は非常に大まかなベンチマークを作成しましたが、2 つの実装の間に違いは見られませんでした。私の 2 番目の仮定は間違っていますか、それとも JVM (自動 TCO を持たない) で実行し、recurそれを達成するためのトリックを使用することに関係がありますか?

ありがとうございました。

この記事に関して質問があります。

このコードの間

そしてこのコード

1) これがどれだけ役立つか、私は混乱しています。2 番目のスニペットには、自分自身を再度呼び出す前に必要なものを計算するため、オーバーヘッドが少ないテール コールが含まれているだけですか?

私が理解しているように、テールコールはまだ排除されておらず、最適化されているだけです。

odds2) そして、odds1とにかく存在する必要があるのはなぜですか? それは私にもまだはっきりしていません。

メソッドがfinalでない限り、Scalaコンパイラが末尾呼び出しの最適化を適用しないのはなぜですか？

たとえば、これは次のとおりです。

結果は

エラー：@tailrec注釈付きメソッドを最適化できませんでした：プライベートでもファイナルでもないため、オーバーライドできます

このような場合にコンパイラがTCOを適用した場合、正確には何がうまくいかないでしょうか。