再帰は一般的に、スタックを使用する場合と比較して、古い方法のトラバースと見なされますか？

Question

私は、人々が再帰の代わりにスタックを使うことを選択しているいくつかの場所で読んできました。これは、再帰が古くなった仕事の仕方であるとみなされるか、あるいは両方の方法が異なるコンテキストで同等に適用できるためですか？

Answer 1

反復されるスタックの使用

もrecursion

参照を除去する標準的な技術であります多くの場合、再帰よりも速く/オーバーヘッドが少なくなります。再帰では、マシンのスタックを暗黙的にスタックとして使用します。これは "無償で"取得しますが、高価な関数呼び出し（およびアテンダントマシンスタック管理）のコストを払っています。

しかし、再帰的な関数は、しばしばより読み書きする方が直感的です。

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

Answer 2

いいえちょうど反対です。再帰は、すべてのクラスの問題を表現する自然な方法です。スタックは再帰を持たない場合にそれをシミュレートする方法です。

例えば、questionを参照してください。あるいは、標準の再帰関数のようなものを考えてみましょう。n番目のフィボナッチ数を計算する。

あなたはFibonacci numbersシリーズF _N = F _のn-1 + F _N-2ように定義された

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

であることを思い出します。
F（0）= 0
F（1）= 1
再帰的ステップ：
F（N）= F（

この

は

ベースケースとして再帰的定義のように書くことができます。 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で記述している場合は、それらの中間結果を追跡するために独自のスタックを管理する必要があります。

Answer 3

には、魚釣りの修正が含まれています。 What is tail-recursion?

末尾再帰（すなわち、反復を使用して除去することができる）の例：

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 
    } 
} 

Answer 4

テールコールがスタックを増やす（テールコール最適化（TCO）が適用されない）プログラミング言語/環境では、深い再帰を避けることが最善であり、スタックデータ構造を使用する可能性のある反復ソリューションは好ましい。

一方、テールコールを使用して反復をサポートする言語/環境にいる場合、または再帰の深さが常に小さい場合、再帰はしばしば洗練された/優雅なソリューションです。

（これは少しオーバー幅広いですが、全体的に、私は決して「時代遅れ」再帰を呼ぶだろう。）

Answer 5

いやいや、私は現代の開発者は、いくつかの上にreadibilityとメンテナンスのしやすさを重視すべきだと思いますミリ秒。

問題が再帰的である場合は、再帰的に解決することをお勧めします。

さらに、反復/積み重ねの解決策を強制するために、いくつかの予期しないバグを導入する可能性があります。