問題タブ [tail-recursion]

これを行うためのhaskellの方法は何ですか?

より多くの背景: 私はオイラー問題 27を解いています。

次のステップは、可能なすべての a と b をループしてタプルのリストを取得し、次の処理を行うことです。

しかし、2つの変数をループする方法がわかりません..ありがとう。

友人がClojureでこのコードスニペットをくれました

そして、同様のScala実装に対してどのようにうまくいくのかと私に尋ねました。

私が書いたScalaコードは次のようになります。

つまり、Clojureのコードは私のマシンで約1.8秒で実行され、5 MB未満のヒープを使用し、Scalaのコードは約12秒で実行され、512 MBのヒープでは不十分です（ 1GBまでヒープ）。

では、なぜこの特定のケースでClojureがこれほど高速でスリムなのか、疑問に思っています。速度とメモリ使用量の点で同様の動作をするScala実装がありますか？

宗教的な発言は控えてください。私の興味は、主にこの場合のclojureの速度を上げる理由と、scalaでのalgoの実装が速いかどうかを調べることにあります。ありがとう。

頭の中でまっすぐにするためだけに。Erlangコードの次の例を考えてみましょう。

test（）呼び出しではなく、gotoですか？

Cで学んだので、関数呼び出しを行うと、戻り位置は常にスタックに置かれるので、これを尋ねます。スタックオーバーフローが発生するため、ここのErlangではこれが当てはまるとは想像できません。

関数を呼び出すには、gotoとgosubの2つの方法がありました。gotoはプログラムフローを別の場所に誘導し、gosubはあなたがどこから来たのかを覚えているので、戻ることができます。

この考え方を考えると、Erlangの再帰をより簡単に見ることができます。なぜなら、私がgotoとしてtest（）を読んだだけなら、まったく問題がないからです。

したがって、私の質問：：Erlangは、スタック上のリターンアドレスを記憶する代わりに、gotoを使用しているだけではありませんか？

編集：

私のポイントを明確にするために：

gotoは、いくつかの言語で使用して、あちこちをジャンプできることを知っています。ただし、someFunction（）を実行する代わりに、次のことも実行できると仮定します。最初の例では、フローが戻るsomeFunction（）に移動し、2番目の例では、フローはsomeFunctionで続行され、決して戻りません。

したがって、メソッドの開始点にジャンプできるようにするだけで、通常のGOTOの動作を制限します。

このように見える場合、Erlangの再帰関数呼び出しはgotoのように見えます。

（私の意見では、gotoは、元の場所に戻ることができない関数呼び出しです）。これはまさにErlangの例で起こっていることです。

x秒ごとにメソッド呼び出し（またはメッセージ送信、適切な用語だと思います）を繰り返すには、NSTimer（NSTimerのscheduledTimerWithTimeInterval:target:selector:userInfo:repeats:）を使用するか、メソッドに再帰的に自分自身を呼び出すようにします最後に (performSelector:withObject:afterDelay を使用)? 後者はオブジェクトを使用しませんが、明確で読みにくいのではないでしょうか? また、私が何をしているのかを説明するために、これは真夜中の 12:00 までカウントダウンするラベル付きのビューであり、0 になると時間 (00:00:00) が点滅します。ビープ音を永遠に再生します。

ありがとう。

編集: また、 SystemSoundID を (永遠に) 繰り返し再生する最良の方法は何でしょうか? 編集:これを使用して SystemSoundID を永遠に再生することになりました:

正常に動作するようです..そして、ラベルの点滅には、私が推測する NSTimer を使用します。

以下を末尾再帰バージョンに変換するにはどうすればよいですか。

分岐は 2^n の大きさであるため、単一のアキュムレータを維持することは不可能のようです。

考えられる解決策は、反復ごとにアキュムレータに新しいアキュムレータをリストに追加させることです。多分上記の解決策は最適ですか？

前もって感謝します。

典型的な以外の再帰関数を設計する言語に依存しない他の方法は何ですか:

他の方法は存在しますか？例を表示するときは常に、上記のコードのバージョンが表示されます。

ありがとう！:)

末尾呼び出しを除去するための再帰関数を常に構築できますか？そうでない場合、スタックサイズを制限する他の戦略は何ですか？

例:( ScalaのBreakまたはFoldの短絡に触発された）

目標は、この特定の機能を選択することではなく、スタックサイズを制限する手法を学ぶための小道具として使用することです。

アップデート

これからの私の持ち帰りは次のとおりです。

問題のドメインが、再帰がスタックサイズの制限に達する可能性があるようなものである場合：

コードを書き直して、scala-compiler-version-of-tailcall-optimizableにします。これは、新しい（2.8）@scala.annotation.tailrecアノテーションによって支援/検証できます。

それが不可能な場合は、反復ループ構造を使用するように書き直してください。

また、この書き直し（どちらの場合も）は、ある程度のスキル/才能/賢さ/練習が必要だと感じています。

Scalaは末尾再帰の最適化をサポートしていますか？

scalac ( Scalaコンパイラ)が末尾再帰を最適化しないのはなぜですか?

これを示すコードとコンパイラの呼び出し:

スタックオーバーフローには、 Scalaで末尾再帰が可能な条件を説明するさまざまな回答があります。制限と、末尾再帰を利用する方法と場所を理解しています。私が理解していない部分は、プライベートメソッドまたはfinalメソッドへの制限が存在する理由です。

Scalaコンパイラが実際に再帰関数をバイトコードレベルで非再帰関数に変換する方法については調査していませんが、次のような動作をすると仮定します。Foo再帰関数を持つクラスがありますmod：

これは基本的なモジュロ関数であり、Scalaコンパイラーが次のような疑似Java-Scalaに変換されると思います。

（私はその翻訳を台無しにしたと信じることができますが、詳細は重要ではないと思います。）

だから今私がサブクラスだとしましょうFoo：

これが機能しなくなるのは何ですか？JVMにとが呼び出されたときFoo/Barに、使用する必要modのある関数の解決に問題があるのはなぜですか。modこれは、基本関数が非再帰的である状況と異なるのはなぜですか？

これが事実であると私が見ることができるいくつかの考えられる理由は次のとおりです。

1. 何らかの理由で、Scalaコンパイラーの実装はこれを処理しません（その場合は十分に公平です。もしそうなら、これを変更する計画はありますか？）

2. 関数内Fooはコンパイル中に変更されるため、実際にはオーバーライドするメソッドはありません。modmod-non-recursiveFoomod