language-agnostic - 命令型言語での再帰の「必要な」使用

Question

最近、いくつかの異なる場所で、「学校で再帰について学びましたが、それ以来、再帰を使用したことも、その必要性を感じたこともありません」というコメントを目にしました。（再帰は、特定のプログラマーグループの間で「本の学習」の人気のある例のようです。）

確かに、JavaやRuby [1]などの命令型言語では、スタックオーバーフローのリスクがあるため、また、これらの言語のほとんどのプログラマーが慣れているスタイルであるため、通常、反復を使用して再帰を回避します。。

厳密に言えば、そのような言語では再帰を「必要に応じて」使用することはできないことを今私は知っています。どんなに複雑なことが起こっても、再帰を反復に置き換えることができます。ここで「必要」とは、次のことを意味します。

再帰が反復よりもはるかに優れていて（明快さ、効率などの理由で）、とにかく再帰を使用し、反復への変換が大きな損失であったような言語のコードの特定の例を考えてみてください。

再帰的に歩く木は、回答の中で何度か言及されています。ライブラリで定義されたイテレータを使用するよりも再帰を改善したのは、その特定の使用について正確に何でしたか。

[1]：はい、これらもオブジェクト指向言語であることを私は知っています。ただし、これはこの質問には直接関係ありません。

score 12 · Accepted Answer

再帰の「必要な」使用法はありません。すべての再帰的アルゴリズムは、反復アルゴリズムに変換できます。スタックが必要だったことを思い出すようですが、頭のてっぺんから正確な構造を思い出せません。

実際には、次の目的で再帰を使用していない場合（命令型言語でも）、少し怒っています。

ツリートラバーサル
グラフ
字句解析/構文解析
並べ替え

score 8 · Accepted Answer

たとえば、あらゆる種類の木構造物を歩いているとき

再帰下降パーサーを使用して文法を解析する
DOMツリーを歩く（たとえば、解析されたHTMLまたはXML）

また、オブジェクトメンバーのtoString（）を呼び出すすべてのtoString（）メソッドも、再帰的と見なすことができます。すべてのオブジェクトシリアル化アルゴリズムは再帰的です。

score 7 · Accepted Answer

私の仕事では、再帰がアルゴリズムに使用されることはめったにありません。階乗などのようなものは、単純なループを使用してはるかに読みやすく（そして効率的に）解決されます。それが表示される場合、それは通常、本質的に再帰的なデータを処理しているためです。たとえば、ツリー構造上のノードを再帰的に処理できます。

たとえば、二分木のノードをウォークするプログラムを作成する場合、1つのノードを処理し、それ自体を呼び出してその子のそれぞれを処理する関数を作成できます。これは、子ノードをループするときに、子ノードごとにすべての異なる状態を維持しようとするよりも効果的です。

score 6 · Accepted Answer

最もよく知られている例は、おそらくCARHoareによって開発されたクイックソートアルゴリズムです。

もう1つの例は、ファイルを見つけるためにディレクトリツリーをトラバースすることです。

score 4 · Accepted Answer

私の意見では、データ構造も再帰的である場合、再帰的アルゴリズムは自然に適合します。

def traverse(node, function):
    function(this)
    for each childnode in children:
        traverse(childnode, function)

なぜそれを繰り返し書きたいのかわかりません。

score 1 · Accepted Answer

再帰は、外部スタックを使用した反復としていつでも書き換えることができます。ただし、スタックオーバーフローにつながるような非常に深い再帰のリスクがないと確信している場合は、再帰は非常に便利です。

1つの良い例は、既知のオペレーティングシステムでディレクトリ構造をトラバースすることです。あなたは通常それがどれくらい深くなることができるかを知っています（最大パス長は制限されています）、そしてそれ故にスタックオーバーフローはありません。外部スタックを使用して反復を介して同じことを行うのは、それほど便利ではありません。

score 1 · Accepted Answer

「なんでもの木」と言われました。私は用心深すぎるかもしれませんし、最近のスタックが大きいことは知っていますが、それでも典型的なツリーでは再帰を使用しません。ただし、バランスの取れたツリーで行います。

score 1 · Accepted Answer

処理しているデータがすべてです。

文字列をデータ構造に変換する単純なパーサーを作成しました。これはおそらく Java での 5 年間の作業の中で唯一の例ですが、それは正しい方法だったと思います。

文字列は次のようになりました。

"{ index = 1, ID = ['A', 'B', 'C'], data = {" +
   "count = 112, flags = FLAG_1 | FLAG_2 }}"

これに対する最良の抽象化は、すべてのリーフノードがプリミティブデータ型であり、ブランチが配列またはオブジェクトであるツリーでした。これは典型的な再帰問題です。非再帰的な解決策も可能ですが、はるかに複雑です。

score 0 · Accepted Answer

レポートのリストがあります。このリストを含むクラスでインデクサーを使用しています。レポートは、インデクサーを使用してスクリーン名で取得されます。インデクサーでは、そのスクリーン名のレポートが存在しない場合、レポートを読み込み、それ自体を再帰的に呼び出します。

public class ReportDictionary
    {
        private static List<Report> _reportList = null;

        public ReportColumnList this[string screenName]
        {
            get
            {
                Report rc = _reportList.Find(delegate(Report obj) { return obj.ReportName == screenName; });

                if (rc == null)
                {
                    this.Load(screenName);
                    return this[screenName]; // Recursive call
                }
                else
                    return rc.ReportColumnList.Copy();
            }
            private set
            {
                this.Add(screenName, value);
            }
        }

    }

これは、追加のコード行を使用して、再帰なしで実行できます。

language-agnostic - 命令型言語での再帰の「必要な」使用

9 に答える 9

Related

Reference