問題タブ [tail-recursion]

OCamlで末尾再帰のリストソート関数を実装しようとしていますが、次のコードを思いつきました。

しかし、「評価中のスタックオーバーフロー（ループ再帰？）」エラーが発生したため、実際には末尾再帰ではないようです。

このコードで末尾再帰ではない呼び出しを見つけるのを手伝っていただけませんか。私はそれを見つけることなく、かなりたくさん検索しました。sortそれは関数のletバインディングですか？

pow()末尾再帰的であり、メモ化を使用して繰り返し計算を高速化する計算アルゴリズムを探しています。

パフォーマンスは問題ではありません。これは主に知的な演習です。電車に乗って、可能な限りさまざまなpow()実装を考え出しましたが、これら 2 つの特性を備えた満足のいく実装を思い付くことができませんでした。

私のベストショットは次のとおりでした。

動作しますが、すべての計算結果を記憶するわけではありません - 指数1..exp/2とexp.

方法は次のとおりです。

このメソッドの可能な出力は次のとおりです（yとnはユーザー入力です）。

線の「私は青」と「私は赤」が印刷されているのはなぜですか？最初に入力され、最後に印刷された赤で逆の順序で印刷されるのはなぜですか？

ネストされたリストに対するフラット化、アトム数のカウントなどは問題ありません。

ところで、私はCPS変換や「ペアツリー」には興味がありません。

C++ で簡単な末尾再帰関数を教えてもらえますか?

末尾再帰が優れているのはなぜですか?

末尾再帰以外にどんな種類の再帰がありますか?

以下の疑似コードの末尾再帰バージョンはありますか? ありがとう ！

Scala 2.8.x では、@tailrecコンパイラが注釈付きメソッドで末尾呼び出しの最適化を実行できない場合にコンパイル時エラーを発生させる新しい注釈 ( ) が追加されました。

に関してClojureに同様の機能はありloop/recurますか？

編集: 私の質問に対する最初の回答(ありがとう、Bozhidar Batsov)を読み、Clojureのドキュメントをさらに検索した後、私はこれに出くわしました:

(recur exprs*)
expr を順番に評価し、並行して、再帰ポイントのバインディングを expr の値に再バインドします。再帰ポイントが fn メソッドの場合、params を再バインドします。再帰ポイントがループの場合は、ループ バインディングを再バインドします。その後、実行は再帰ポイントに戻ります。recur 式は、再帰ポイントのアリティと正確に一致する必要があります。特に、再帰ポイントが可変引数 fn メソッドの先頭にある場合、残りの引数の収集はありません。単一の seq (または null) を渡す必要があります。末尾位置以外での再発はエラーです。

recur は、Clojure でスタックを消費しない唯一のループ構造であることに注意してください。末尾呼び出しの最適化はなく、未知の境界のループに自己呼び出しを使用することは推奨されません。recur は機能的であり、末尾位置での使用はコンパイラによって検証されます[強調は私のものです]。

このHaskellべき関数の末尾再帰をどのように作成しますか？

ループを解除するにはどうすればよいですか？

ネストされたforループを末尾再帰に変換するにはどうすればよいですか？

22ページのFOSDEM2009http ://www.slideshare.net/Odersky/fosdem-2009-1013261でのScalaTalkから：

中断して続行Scalaにはそれらがありません。なんで？それらは少し必須です。多くの小さな関数をより適切に使用するクロージャーと対話する方法を発行します。それらは必要ありません！

説明は何ですか？

リストをパラメーターとして関数に再帰的に要素を追加する関数に渡し、再帰が発生したときにリストを変更しないようにするにはどうすればよいですか？

再帰の各レベルでリストを使用し、より深い再帰レベルで値が追加されたリストを使用したいと思います。

具体的には、グラフでDFS検索を実行し、アクセスしたノードをリストに格納します。