問題タブ [recursion]

練習プロジェクトの 1 つにツリー タグを実装しています。このタグでは、ディレクトリの内容をツリー形式で (再帰的に) 表示します。私は、JSP2.0 より前の時代に、Java でカスタム タグと同様の要件を実装していました。ディレクトリの処理には再帰が必要です (サブディレクトリを処理するため)! これをタグファイルとしてコーディングすることは可能で、再帰的に使用できますか?

コードはそのままで問題なく動作するため、これは一種の頭の体操のような質問です。私自身の脳が今私を失敗させているので、私はスタックオーバーフローに目を向けています。

Google Maps JS API を使用して住所を検索し、地図上にマーカーを配置するコード スニペットを次に示します。ただし、最初のルックアップが失敗する場合があるため、別のアドレスでプロセスを繰り返したいと考えています。

( の 2 番目のパラメーターgetLatLngはコールバック関数です。)

もちろん、マップを中心に合わせてズームし、マーカーを追加する 3 つの行が重複していることがわかります。1 回はプライマリ コールバックで、もう 1 回は「フォールバック コールバック」です (笑)。冗長性なしで全体を表現する方法を見つけることができますか? あなたのソリューションが任意の数のバックアップ マップ文字列に対して機能する場合、ボーナス ポイントを獲得できます。

リストの再帰的なリストを作成すると:

その後、tempList.Clear() を呼び出します。メモリ内のすべての childLists を破棄しますか?それとも最初にすべての childLists をクリアする再帰メソッドを作成する必要がありますか?

非常に簡単に言えば、テールコール最適化とは何ですか?

より具体的には、適用できる小さなコード スニペットと、適用できない小さなコード スニペットと、その理由の説明を教えてください。

現在、SQL Server SQL ステートメントを同等の ANSI 汎用ステートメントに変換していますが、WITH ステートメントを使用した再帰ステートメントに悩まされています。

この問題に集中するために、次のように問題を単純化します。

テーブルが 2 つある場合

1. 報告単位

   • col1: キー
   • col2: ParentReportingUnitKey

2. 施設

   • col1: キー
   • col2: ParentReportingUnitKey

この構造は、施設までのレポーティング ユニットの階層を記述しています。レポーティング ユニットは、0 .. 1 の直接の親レポーティング ユニットと 0 .. n の子レポーティング ユニットを持つことができます。

施設は、レポーティング ユニットにリンクする「リーフ」レコードです。

ANSI 92 の有効な SQL ステートメント (または、最悪の場合、Oracle、DB2、および SQL Server で動作するもの) を作成する必要があります。これは、階層の任意の場所にある特定のレポート ユニットに関連するすべての機能を返します。

例えば

• ReportingUnit R1 には ReportingUnit の子 R1.1 と R1.2 があります
• ReportingUnit R1.1 には子 R1.1.1、R1.1.2 があります

• ReportingUnit R1.2 には子 R1.2.1、R1.2.2 があります

• 施設 F1 には、親報告単位 R1.1.1 があります。

• 施設 F2 には、親報告単位 R1.1.2 があります。
• 施設 F3 には、親報告単位 R1.2.1 があります。
• 施設 F4 には、親報告単位 R1.2.2 があります。

ReportingUnit テーブルには 0 ～ n レベルの再帰がある可能性があることを念頭に置いて、パラメーター ReportingUnit=R1 を指定して SQL ステートメントから 4 つの機能すべてを返すにはどうすればよいでしょうか?

どういうわけか、この関数を一定のスタックスペースを使用するように書き直す良い方法を考えるのに苦労しています。フィボナッチ関数を使用し、その特定の問題の特性を利用することにより、ツリー再帰のチートに関するほとんどのオンラインディスカッションが行われます。この「現実世界」（フィボナッチ数列よりも現実世界）での再帰の使用について何かアイデアはありますか？

Clojureは、末尾呼び出しの最適化がなく、「recur」特殊形式による末尾再帰のみを備えているため、興味深いケースです。また、可変状態の使用を強くお勧めしません。tree-seqを含む多くの怠惰な構造がありますが、この場合にどのように役立つかはわかりません。C、Scheme、Haskell、または他のプログラミング言語から習得したいくつかのテクニックを誰かが共有できますか？

編集：コメントでリクエストして...

一般的な用語で言い換えると、Schemeを使用します-スタックスペースを消費したり、非自己呼び出しの末尾呼び出しの最適化を必要としないように、次の再帰パターンを書き直すにはどうすればよいですか？

x、macerate、frobnicate、f、g、またはhの代数的特性に依存しない答えを探しているという点を理解するために、迷惑な名前を選びました。再帰を書き直したいだけです。

更新：

Rich Hickeyは、Clojureに明示的なトランポリン機能を追加してくれました。

プロジェクトで（GNU）Makeを使用しています。私は現在、ディレクトリごとに1つのmakefileを配置し、SUBDIRSを使用してサブディレクトリを指定しています。これはmakeを使用する理想的な方法ではなく、1つのトップレベルのmakeファイル（または複数の、includeを使用して分割）を使用することをお勧めします。過去にこのレイアウトを移行/使用してみましたが、不必要に複雑に見えます。

再帰的なmakefileを使用することの利点/欠点はどれですか？

Suckerfish css メニューと Jquery を使用してテーブルからメニューを作成しようとしています。私はこれを参照として使用しています: ASP.NET と JQueryを使用した Suckerfish メニューと、手動で提供されたリンク (記事のように) を使用しています。

私が問題を抱えているのは、データベースからメニュー項目を取得し、適切な階層に新しいメニュー項目を作成する再帰関数を作成することです。私のデータベーステーブルは次のようになります:

テーブルメニュー

MenuID ParentID リンク テキスト

アイテムが親レベルのアイテムである場合、MenuID と ParentID は同じであり、子の場合は ParentID フィールドに親の MenuID が含まれるという考えです。親のすべての子を調べて見つけることができる関数を作成する必要があります (いくつかのレベルになる可能性があります)。次のような手動エントリを置き換えます。

私は必要に応じてデータベースのテーブル構造を変更し、基本的にこれを実現するために他のことを何でもします。

ご意見をお寄せいただきありがとうございます。

私は、変数が変更されたときに、それらの変数に依存するすべての関数 (およびそれらの関数に依存する関数など) が同時に更新されるように、単純な関数を一緒にバインドできるようにする実験的な関数エバリュエーターを作成しました。これを行う方法は、関数が入力されたときにすぐに関数を評価するのではなく、関数を保存することです。出力値が要求されたときのみ関数を評価し、出力値が要求されるたびに評価します。

例えば：

'pi' と 'rad' を変数 (定数を返す関数) として定義し、'area' と 'perim' を関数として定義します。「pi」または「rad」のいずれかが変化するたびに、「area」と「perim」の結果も同じように変化することを期待しています。同様に、「面積」または「周縁」に依存する関数があれば、それらの結果も変化します。

これはすべて期待どおりに機能しています。ここでの問題は、ユーザーが偶発的または意図的に再帰を導入した場合です。私の文法には論理がありません - それは単なる評価器です - そのため、ユーザーに再帰から「抜け出す」方法を提供することはできません。私はそれがまったく起こらないようにしたいと思っています。つまり、それを検出し、問題のある入力を無効であると宣言する方法が必要です。

例えば：

現在、最後の行を評価すると StackOverflowException が発生します (最初の 2 行は「0」と評価されますが、宣言されていない変数/関数は 0 に等しくなります)。私がやりたいことは、循環論理の状況を検出し、ユーザーがそのようなステートメントを入力することを禁止することです。循環ロジックがどれほど深く隠されているかに関係なく、これを実行したいのですが、どうすればよいかわかりません。

ちなみに、舞台裏では、入力文字列は単純なスキャナーを介してトークンに変換され、次に手書きの再帰降下パーサーを介して抽象構文ツリーに変換され、AST が評価されます。言語は C# ですが、コード ソリューションを探しているわけではありません。ロジックだけで十分です。

注: これは、パーサーとコンパイラーがどのように機能するかを学ぶために私が使用している個人的なプロジェクトであるため、ミッション クリティカルではありません。皆さんが提供できるどんな助けも大歓迎です。=)

編集: 誰かが興味を持っている場合は、私のブログのこの投稿で、私がこれを学ぼうとしている理由と、そこから何を得ているかを説明しています。

次の列を持つサイトマップ階層を含む DataTable があります。

• アイテム ID
• 親ID
• 名前
• URL

HTML でネストされたリストのセットを生成する必要があります (わかりやすくするためにアンカー要素を省略しています)。

ツリーには、「現在の」ノード/ページにつながるブランチのみが含まれている必要があります（したがって、上記の例を使用すると、アイテム「1」または「3」が持つ子アイテムは表示されません。疑似コード/コード例を手伝ってくれる人はいますかリーフからルートまでツリーをたどって、HTML を構築できますか?ありがとう。