問題タブ [recursion]

Thread.getAllStackTraces（）を使用してスタックトレースを取得できることを知っています（Mapを返しますが、clearは機能しません）。再帰メソッドを実行すると、スタックトレースが大きすぎるために例外が発生する可能性がありますが、それをクリアする方法はありますか？

私は疑問に思っています-次のようなものを解析する最も効果的な方法は何ですか:

もちろん、これは最終的にいくらかのテンプレート システムになることを意図しているので、私の計画は、このようなものとして、テンプレートを「配置」するハッシュマップを作成することです。

「セクション」(# で始まるタグ) は複数回繰り返すことができることに注意してください。

また、任意のセクションには、任意の数の他のセクションと通常のタグを含めることができます...

それで..どうやってやったの？

再帰を使用して、指定されたリストの逆を返す関数が必要です。どうやってやるの？

最近、再帰について勉強しています。再帰と再帰は同じものだとしばらく考えていましたが、最近の宿題や小テストの問題で、「再帰」が方法であるというわずかな違いがあると思いました。再帰的なプログラムまたは関数を記述します。

問題やプログラムの「再帰」を記述するために使用される「マスター定理」と呼ばれるものがあることに最近気付くまで、これはすべて私にとって非常にギリシャ語でした。ウィキペディアのページを読んでいるのですが、いつものように、何を言っているのかよくわからないような言葉遣いで書かれています。私は例を使ってはるかによく学びます。

いくつかの質問があります: この繰り返しが与えられたとしましょう:

r(n) = 2*r(n-2) + r(n-1);
r(1) = r(2) = 1

これは実際、マスター定理の形をとっているのでしょうか? もしそうなら、それは言葉で何を言っているのですか？この再帰に基づいて小さなプログラムまたは再帰ツリーを作成しようとすると、どのようになりますか? 数値を代入してパターンを確認し、そのパターンを再帰的に作成できる疑似コードを作成するだけでよいでしょうか、それともマスター定理の形式である可能性があるため、より簡単な数学的アプローチはありますか?

ここで、前回の再帰から作成されたプログラムによって実行された追加の回数の再帰 T(n) を求めるよう求められたとします。基本ケースはおそらく T(1) = T(2) = 0 になることがわかりますが、そこからどこへ行くべきかわかりません。

基本的に、私は特定の繰り返しからコードに移行する方法とその逆を求めています。これはマスター定理のように見えるので、簡単で数学的な方法があるかどうか疑問に思っています。

編集：さて、過去の課題のいくつかを調べて、「再発を見つける」ように求められた別の例を見つけました。これは、投稿の問題を抱えているこの質問の一部です。

次のプログラム フラグメントの加算演算の数を最適な方法で記述する再帰 (l == 1 および r == n で呼び出した場合)

Windows システムで特定の正規表現に一致するファイルまたはディレクトリを除くサブディレクトリを含むディレクトリをコピーするにはどうすればよいですか?

これは簡単な修正かもしれませんが、バイナリ サーチ ツリーのすべてのノード (Node クラスの Size プロパティ) を合計しようとしています。以下の私の BST クラスには、これまでのところ次のものがありますが、0 が返されます。

Node クラス内には、指定されたプロパティに Size と Name を格納する Data があります。私は全体のサイズを合計しようとしています。提案やアイデアはありますか？

計算するための非再帰的アルゴリズムをどのように記述しますn!か？

私は最近 Python の学習を始めましたが、(デフォルトで) 1000 の深い再帰制限を見つけてかなり驚きました。30000 くらいに設定すると、C と同じようにセグメンテーション違反でクラッシュします。ただし、C はかなり高くなるようです。

(Python 関係者は、いつでも再帰関数を反復関数に変換でき、常に高速であるとすぐに指摘します。それは 100% 真実です。しかし、それは実際には私の質問の内容ではありません。)

Perl で同じ実験を試みたところ、約 1000 万回の再帰で 4 ギガの RAM がすべて消費され、^C を使用して試行を停止しました。明らかに、Perl は C スタックを使用しませんが、再帰の際に途方もない量のメモリを使用します。関数を呼び出すためにどれだけの作業をしなければならないかを考えると、それほど衝撃的ではありません。

Pike で試してみたところ、約 2 秒で 100,000,000 回の再帰が得られたことに完全に驚きました。それがどのように行われたかはわかりませんが、反復プロセスへの再帰を平坦化したのではないかと思います-実行中に余分なメモリを消費していないようです. [注: Pike は些細なケースを平坦化しますが、より複雑なケースでは segfault を実行します。そう言われています。]

私はこれらの無用な機能を使用しました：

他の言語 (PHP、Ruby、Java、Lua、Ocaml、Haskell など) が再帰をどのように処理するのか、またなぜそのように処理するのか、非常に興味があります。さらに、関数が「末尾再帰」である場合に違いが生じるかどうかに注意してください (コメントを参照)。

入力テキスト ボックス、ボタン、および複数行の出力テキスト ボックスを備えた WinForms アプリがあります。テキスト ボックスにルート パスが入力されます。ボタンをクリックすると、すべてのサブディレクトリを再帰的にチェックして、適切なディレクトリ名の検証チェックを行う関数が呼び出されます。結果は複数行のテキスト ボックスに出力されます。

再帰的な作業が別のクラスで行われる場合、次の 2 つのオプションがあります。

1. クラス プロパティ (ArrayList など) で不適切なディレクトリを追跡し、完了したら ArrayList を返し、すべての結果で出力テキスト ボックスを更新します。

2. 出力テキスト ボックスを ByRef に渡し、不適切なディレクトリごとに更新/更新します。1 と 2 はシングル スレッドですが、2 を使用すると、少なくともディレクトリごとに結果が更新されます。

再帰的な作業がプレゼンテーション層で行われ、検証が別のクラスで行われる場合、マルチスレッド化できます。

よりクリーンな方法はどれですか?

誰かがこれを行うためのよりスマートな方法を持っていますか? これより簡単なはずですが、メンタルブロックがあります。基本的に、辞書からアイテムを削除し、辞書でもあるアイテムの値に再帰する必要があります。

アクション辞書は次のようになります。