問題タブ [recursion]

メーリング リストやオンライン ディスカッションで定期的に取り上げられるトピックの 1 つは、コンピューター サイエンスの学位を取得することのメリット (またはメリットの欠如) です。否定派にとって何度も出てくる議論は、彼らは何年もコーディングをしており、再帰を一度も使用したことがないというものです。

質問は次のとおりです。

1. 再帰とは
2. 再帰はいつ使用しますか?
3. なぜ人々は再帰を使わないのですか?

今朝、私はSteve Yegge の: When Polymorphism Failsを読んでいたとき、彼の同僚が Amazon での面接に来た潜在的な従業員に尋ねていた質問に出くわしました。

実際のポリモーフィズムの例として、古典的な「eval」インタビューの質問を見てみましょう。これは (私の知る限り) Ron Braunstein によって Amazon にもたらされました。OOP 設計、再帰、バイナリ ツリー、ポリモーフィズムとランタイム タイピング、一般的なコーディング スキル、および (さらに難しくしたい場合は) 解析理論など、さまざまな重要なスキルを調べることができるため、この質問は非常に豊富です。 .

ある時点で、志願者は、「+」、「-」、「*」、「/」などの二項演算子のみを使用していると仮定して、算術式を二分木として表現できることに気付きます。リーフ ノードはすべて数値であり、内部ノードはすべて演算子です。式を評価することは、木を歩くことを意味します。候補者がこれに気付いていない場合は、そっと誘導するか、必要に応じて伝えることができます。

と言ってしまっても、やはり面白い問題です。

質問の前半は、一部の人々 (名前は息が詰まるまで守りますが、イニシャルはウィリー・ルイスです) は、自分自身を開発者と呼んで Amazon で働きたい場合の仕事の要件であると感じていますが、実際にはちょっと難しいです。 . 問題は、「2 + (2)」などの算術式 (文字列など) から式ツリーにどのように移行するかです。ある時点で、この質問に対する ADJ チャレンジが行われる可能性があります。

後半は、これが 2 人のプロジェクトで、あなたのパートナー ("ウィリー" と呼びます) が文字列式をツリーに変換する責任があるとしましょう。簡単な部分を取得します。ウィリーがツリーを構築するクラスを決定する必要があります。任意の言語で実行できますが、いずれかを選択するようにしてください。そうしないと、ウィリーがアセンブリ言語を渡してくれます。彼が気難しいと感じているのは、もはや生産されていないプロセッサーのためでしょう。

どれだけ多くの候補者がこれを好んでいるかに驚かれることでしょう。

答えは言いませんが、Standard Bad Solution には、switch または case ステートメント (または単に古き良きカスケード if) の使用が含まれます。Slightly Better Solution には、関数ポインターのテーブルの使用が含まれ、おそらく最善の解決策には、ポリモーフィズムの使用が含まれます。いつかやり遂げることをお勧めします。楽しいもの！

それでは、3 つの方法すべてで問題に取り組みましょう。"2 + (2)" などの算術式 (文字列など) から、カスケード if、関数ポインターのテーブル、および/またはポリモーフィズムを使用した式ツリーにどのように移行しますか?

1 つ、2 つ、または 3 つすべてに自由に取り組んでください。

[更新: ほとんどの回答に一致するようにタイトルを変更しました。]

たとえば、n 番目のフィボナッチ数を計算するコードを見てください。

このコードの問題は、(ほとんどのコンピューターで) 15 を超える数値に対してスタック オーバーフロー エラーが発生することです。

fib(10) を計算しているとします。このプロセスでは、 fib(5) が何度も計算されるとします。これをメモリに保存して高速に取得し、再帰の速度を上げる方法はありますか?

ほとんどすべての問題で使用できる一般的な手法を探しています。

Directory.GetFiles() または同様のメソッドですべての結果をループすることなく、特定の種類のファイルの数を見つける方法はありますか? 私はこのようなものを探しています:

Directory.GetFiles を呼び出す再帰関数を作成できることはわかっていますが、すべての反復なしでこれを実行できれば、はるかにクリーンになります。

編集:自分自身を再帰して反復せずにこれを行うことができない場合、それを行う最善の方法は何ですか?

Lisp を学び始めているときに、末尾再帰という用語に出くわしました。正確にはどういう意味ですか？

文字列を 1 文字ずつ処理し、それを解析してツリーのような構造を作成する再帰アルゴリズムがあります。パーサーが現在いる文字インデックスを追跡できるようにしたいのですが (他の何よりもエラーメッセージについて)、複数の返された型を処理するタプルのようなものを実装することに熱心ではありません。

メソッドの外側で宣言され、再帰メソッドに渡された Integer 型を使用しようとしましたが、それは最終的なものであるため、戻ったときに再帰呼び出しのインクリメントは「忘れられます」。(整数値の増分により、値渡しオブジェクトの参照ポイントが新しいオブジェクトになるため)

私のコードを汚染しないような仕事に似たものを得る方法はありますか?

以下のコードでは、SQL Server 2005 で再帰的な CTE (Common Table Expression) を使用して、基本的な階層構造の最上位レベルの親を見つけようとしています。この階層のルールは、すべての CustID に ParentID があり、CustID に親がない場合、ParentID = CustID であり、それが最上位レベルです。

したがって、tblCustomer が次のようになっている場合:

上記のコードから得られる結果は次のとおりです。

私が欲しいのは、その結果の最後の行だけです:

CTE で生成された最後のレコード (最高レベルの CustID) を返すにはどうすればよいですか?

また、このテーブルには関連のない CustID 階層が複数あるため、単に SELECT * FROM tblCustomer WHERE ParentID = CustID を実行することはできません。ID 番号は階層のどこにあるかに関連していないため、ParentID または CustID で注文することはできません。

製品品質の VC++ コードを記述する場合、再帰の使用は許容されますか? なぜですか、そうでないのですか？

再帰を使用せずにRuby on Railsのacts_as_nested_setの任意のノードからJSONハッシュを返す高速でクリーンな方法はありますか?

参照用の再帰的ソリューションは次のとおりです。

次の形式の XML ファイルがあります。

C#を使用してファイルをトラバースする方法について誰か教えてください。