3

私は、人々が再帰の代わりにスタックを使用することを選択しているいくつかの場所で読んでいます。これは、再帰が仕事を成し遂げるための時代遅れの方法であると見なされているためですか、それとも両方の方法が異なるコンテキストで等しく適用可能であるためですか？

4

5 に答える 5

15

いいえ。正反対です。再帰は、問題のクラス全体を表現するための自然な方法です。スタックは、再帰がない場合にそれをシミュレートする方法です。

たとえば、この質問を参照してください。または、標準的な再帰関数の一種を考えてみましょう。n番目のフィボナッチ数を計算します。

フィボナッチ数がシリーズであることを思い出してください

0,1,1,2,3,5,8,13, ...

F n = F n-1 + Fn-2となるように定義されます。

これは、再帰的定義として次のように記述できます。

基本ケース：
F（0）= 0
F（1）= 1
再帰ステップ：
F（n）= F（n-1）+ F（n-2）

したがって、F（0）= 0、F（1）= 1、F（2）= F（0）+ F（1）=1などになります。

これを計算するための簡単なプログラム（Cではニヤリと）は次のとおりです。

int fib(int n) {
    /* we'll ignore possible negative arguments, see Wikipedia */
    switch(n) {
       case 0: return 0; break;
       case 1: return 1; break;
       default: return fib(n-1)+fib(n-2); break;
    }
}

そのプログラムが元の定義にどれほど密接に対応しているかに注意してください。

重要なのは、Cが呼び出しスタック内のすべての中間結果を管理することです。一部の言語はそれを行うように定義されていません（私が手に負えないと考えることができる唯一の言語は古いFORTRANですが、他の言語もあると確信しています）。アセンブラまたは古いFORTRANで記述している場合は、それらの中間結果を追跡するために独自のスタックを管理する必要があります。

于 2009-04-28T01:34:31.893 に答える
10

多くの場合、反復は再帰よりも高速/オーバーヘッドが少なくなります。再帰を使用すると、暗黙的にマシンのスタックをスタックとして使用します。これは「無料」で取得できますが、高価な関数呼び出し（および付随するマシンスタック管理）のコストを支払います。

しかし、再帰関数は、多くの場合、書き込みと読み取りがより直感的です。

多くの場合、再帰を使用して関数を記述し、それがボトルネックになるまでそのままにしてから、明示的なスタックを使用する反復関数に置き換えることができます。

于 2009-04-28T01:36:21.310 に答える
6

フィッシュリップの修正を含むように更新されました。

スタックの使用は、再帰を排除するための標準的な手法です

参照：末尾再帰とは何ですか？

末尾再帰の例（反復を使用して削除できます）：

public class TailTest
{   
    public static void Main()
    {       
        TailTest f = new TailTest();
        f.DoTail(0);
    }

    public void DoTail(int n)
    {       
        int v = n + 1;      
        System.Console.WriteLine(v);    

        DoTail(v);   // Tail-Recursive call
    }
}
于 2009-04-28T01:35:05.760 に答える
4

末尾呼び出しがスタックを増大させるプログラミング言語/環境（末尾呼び出し最適化（TCO）が適用されていない）を使用している場合は、深い再帰を回避するのが最善であり、スタックデータ構造を使用する可能性のある反復ソリューションが推奨されます。

一方、末尾呼び出しでの反復をサポートする言語/環境を使用している場合、または再帰の深さが常に小さい場合、再帰は多くの場合、優れたエレガントなソリューションです。

（これは少し広範ですが、全体として、再帰を「時代遅れ」とは決して呼びません。）

于 2009-04-28T01:37:11.340 に答える
3

いいえ、現代の開発者は数ミリ秒の読みやすさとメンテナンスの容易さを重視すべきだと思います。

問題が再帰的である場合は、ソリューションを再帰的にすることを強くお勧めします。

さらに、反復/スタックソリューションを強制しようとして、予期しないバグが発生する可能性があります。

于 2010-04-16T15:56:30.960 に答える