問題タブ [tail-recursion]

JavaScriptで実装した末尾再帰パスファインディングアルゴリズムがあり、（すべて？）ブラウザでスタックオーバーフロー例外が発生する可能性があるかどうかを知りたいです。

次のようなhaskell式を考えてみましょう:(重要な例、明白な方法が何であるかを教えてはいけません！;）

この関数は末尾再帰ではないため、次のように書くこともできます。

（この表現には何も問題がないことを願っています）

私が聞きたいのは、これらの解決策のどれが優れているかということです。最初のソリューションの利点は、部分的に非常に簡単に評価できることです（Haskellは最初のソリューションで停止する:必要がないため）が、2番目のソリューションは（明らかに）末尾再帰ですが、私の意見では完全に評価する必要がありますあなたが何かを出すことができるまで。

これの背景は私のBrainfuckパーサー（私の最適化の質問を参照）です。これは非常に醜い（さまざまなreverse命令... ooh）実装されていますが、最初の方法で簡単に実装できます-これを「セミテール再帰」の方法と呼びましょう。

単純な場合もありますが (自己呼び出しが最後のステートメントの場合は末尾再帰です)、それでも混乱する場合があります。「自己呼び出しの後に実行する命令がない場合は、末尾再帰です」と教授に言われました。これらの例はどうですか (あまり意味がないという事実は無視してください):

a) これは、自己呼び出しが最後のステートメントであり、その後に実行するものが残っていないことを確認して、末尾再帰にする必要があります。

b) でも、これはどうですか？条件が真の場合、それ以外は何も実行されないため、末尾呼び出しにする必要がありますが、最後のステートメントではありませんか?

c) これはどうですか？どちらの場合も、自己呼び出しが最後に実行されます。

理論的には、大きな入力でもうまく機能するはずの深く再帰的な関数があります。問題は、これを書いている時点で、C# はテール コールの最適化がうまくいかないことを忘れていたことですStackOverflowException。メソッドの基本構造は 2 つの大きなメソッドで構成され、それぞれが他方を呼び出します。

IsSimpleとの両方ProcessExpansionのスタック深度は比較的固定されています。唯一の問題は、Simplify と Expand の間の再帰です。ここでスタックの深さを減らすにはどうすればよいでしょうか?

結果を計算するデリゲートを返すことを考えていましたが、それはやり過ぎのようです - もっと簡単な方法があるはずです。これは私の解決策の考えです（ここでひどく間違ったことをしているに違いないと考え続けているため、あまり洗練されていません）：

だから私の2つの質問は次のとおりです。

1. このソリューションでひどく間違っていると感じるのは何ですか?
2. より良いものを考えられますか？

遺伝的アルゴリズムを使用して、三目並べのすべての可能なゲームを再帰的に再生し、（勝ち、負け、引き分け）のタプルを返す関数を作成しようとしています。ただし、以下の関数は、次のように呼び出されると常にスタックをオーバーフローします。

ここplayersで、は染色体のリストです。オーバーフローは、1人のプレーヤーだけでは発生しませんが、2人のプレーヤーでは発生します。

編集：関数が次のように呼び出された場合、スタックはオーバーフローしません。

ただし、次の方法ではスタックがオーバーフローします。

参考までに、ScoredPlayerは次のように定義されます（文字列はプレーヤートークン、[Int]は染色体、Floatはスコア）：

Haskellについて私が知っていることから、私が使用している呼び出しは関数の結果に対してさらに処理を実行しているplayAll'ため、関数は末尾再帰ではありません。ただし、可能なすべてのゲームを確実にプレイする必要があるため、呼び出しfoldl'を削除する方法がわかりません。foldl'関数を末尾再帰になるように（または少なくともスタックをオーバーフローさせないように）再構築する方法はありますか？

事前に感謝し、大量のコードリストをお詫びします。

重複の可能性：
再帰はループよりも高速ですか？

私は約15年前に、Cで真剣にプログラムするように最初に訓練されました。私の雇用主は、計算が難しいタスクのために高度に最適化されたコードを望んでいました。「再帰のオーバーヘッド」を回避するために、読みやすさを犠牲にしても、再帰をループとして書き直すように何度もアドバイスされたことを覚えています。そのとき私が理解したように、再帰オーバーヘッドは、データをスタックにプッシュし、後でそれをポップオフするために必要な余分な労力でした。

今、私はC、Python、Perl、そして時にはJavaでコーディングしていますが、再帰について時々疑問に思います。それらを書き直すことで得られるものはまだありますか？それらが末尾再帰である場合はどうなりますか？最近のコンパイラはこれらすべての問題を解決しましたか？そのような懸念は通訳言語には無関係ですか？

末尾再帰を使用して C(n,k) を見つける関数をプログラムしたいのですが、助けていただければ幸いです。

私はこれに達しました：

二項係数の次のプロパティを使用します。

しかし、最後の命令が製品であるため、再帰呼び出しを各インスタンスによって実行される最後の命令にする方法がわかりません。唯一の方法だと思う補助機能を使って試してみましたが、解決策が見つかりませんでした。

Haskellの末尾再帰を理解しようとしています。私はそれが何であるか、そしてそれがどのように機能するかを理解していると思いますが、私は物事を台無しにしないことを確認したいと思います。

「標準」の階乗の定義は次のとおりです。

たとえば、実行しているときfactorial 3、私の関数はそれ自体を3回呼び出します（与えるか取るか）。スタックオーバーフローが発生する可能性があるため、階乗99999999を計算したい場合、これは問題を引き起こす可能性があります。到達した後factorial 1 = 1、スタックに「戻って」すべての値を乗算する必要があるため、6つの操作があります（関数自体を呼び出すための3つと、値を乗算するための3つ）。

ここで、別の可能な階乗実装を示します。

これも再帰的です。自分自身を3回呼び出します。しかし、関数の引数としてすでに結果を渡しているので、すべての結果の乗算を計算するために「戻ってくる」必要があるという問題はありません。

これは、私が理解していることですが、末尾再帰についてです。今では、最初のものよりも少し良いように見えますが、それでもスタックオーバーフローを簡単に発生させることができます。Haskellのコンパイラは、末尾再帰関数を舞台裏でforループに変換すると聞いています。それが末尾再帰関数を実行することで報われる理由だと思いますか？

それが理由である場合、コンパイラがこの賢いトリックを実行しないのであれば、関数を末尾再帰にしようとする必要はまったくありません-私は正しいですか？たとえば、理論的にはC＃コンパイラは末尾再帰関数を検出してループに変換できますが、現在はそれを行わないことを私は知っています（少なくとも私が聞いたことはそうです）。したがって、関数を末尾再帰にすることには、今日ではまったく意味がありません。それですか？

ありがとう！

そのため、特定の N 要素セットからすべての k 要素サブセットを見つけようとするこの問題に悩まされています。式 C(n,k)=C(n-1, k-1)+C(n-1, k) を使用して k-subset の総数を知っており、それを行う方法も考えています繰り返しますが、再帰的な解決策を考えようとすると行き詰まります。誰でも私にヒントを与えることができますか？ありがとう！

自然数の階乗 ( より大きいか等しい任意の数0) は、その数にそれ自体の階乗から 1 を引いたものを掛けたものです。ここで、の階乗は0として定義され1ます。

例えば：

1これを書く別の方法は、との間のすべての自然数を掛けることnですn!。

これを F# の再帰関数で表現するにはどうすればよいですか? そして、再帰関数でそれを行う必要がありますか?