再帰的な解決策しか持たない問題はありますか？

Question

重複の可能性：
Is there a problem that has only a recursive solution?
Can every recursion be converted into iteration?
“Necessary” Uses of Recursion in Imperative Languages

のみ再帰的な解決策、つまり、再帰的な解決策を持っている問題が、反復解法を持っている問題がありますまだ発見されていないか、またはより良いが、存在しないことが証明されている（明らかに、これは尾部再帰ではない）。

Answer 1

Ackermann functionは再帰

Answer 2

すべての非np完全問題は、シーケンス、決定、および繰り返しだけで解決できます。再帰は必須ではありませんが、通常は問題が大幅に簡素化されます。

Answer 3

引数をスタックにプッシュして関数呼び出しを置き換え、スタックからポップして戻り、再帰を排除しました。

編集：再帰的なアルゴリズムが一定の間隔で実行できる場合

を「スタックを使用すると、スペースコストを削減しない」に応答して、それは末尾再帰的に書き込むことができます。 tail-recursive形式で記述されていれば、適切なコンパイラがスタックを折りたたむことができます。しかし、これは、 "明示的なスタックプッシュへの関数呼び出しの変換"メソッドも一定のスペースを取ることを意味します。一例として、階乗をとることができます。

階乗：

def fact_rec(n): 
    ' Textbook Factorial function ' 
    if n < 2: return 1 
    else:  return n * f(n-1) 


def f(n, product=1): 
    ' Tail-recursive factorial function ' 
    if n < 2: return product 
    else:  return f(n-1, product*n) 

def f(n): 
    ' explicit stack -- otherwise same as tail-recursive function ' 
    stack, product = [n], 1 
    while len(stack): 
     n = stack.pop() 
     if n < 2: pass 
     else: 
      stack.append(n-1) 
      product *= n 
    return product 

stack.pop（）は、ループ内で）（stack.appendに追従するので、スタックがその中に複数の項目を有することがない、そしてそれは、一定の空間を満たします要件。長さ1のスタックの代わりに一時変数を使用すると想像するなら、それはあなたの標準反復法のアルゴリズムになります。

もちろん、末尾再帰形式では書き込めない再帰関数があります。何らかのスタックを使って反復フォーマットに変換することはできますが、スペースが複雑であることが保証されていれば驚くでしょう。

Answer 4

それはそれは問題を解決するために取るために起こっているどのように多くのコードの行に降りてくる...

リストのすべてのあなたのC上のファイル：なし、その後再帰を使用して\。確かにそれを両方の方法で行うことができますが、理解してデバッグするのがずっと簡単になる方法もあります。

Answer 5

いいえ再帰はスタックにすぎず、明示的にスタックを実装することで同じ結果を得ることができます。

これは特に満足できる回答ではないかもしれませんが、より具体的な質問をしてより良い回答を得る必要があります。例えば、理論はコンピューティングのレベルでは、whileループと（伝統的な）forループしか持たない場合に解決できる問題の範囲にかなりの違いがあると規定しています。

Cスタイルの（...; ...; ...）ループは偽装のwhileループですが、本当に特定の回数反復するループを意味するため、「伝統的」と言います。

Answer 6

のプログラミングでは、再帰は本当に繰り返しの特殊なケースです。つまり、コールスタックを特殊な格納方法として使用する場合です。再帰的メソッドを反復的メソッドに書き換えることができます。それはより複雑であるかもしれないし、よりエレガントではないかもしれないが、それは同等である。数学で

、答えに到達する再帰的な技術を必要とする特定の問題がある - いくつかの例等素数、グラフの最適化を、コンピューティング、（Newton's Method）根を見つけているが、しかし、ここでも、ちょうど質問があります「反復」と「再帰」という用語を区別する方法。

EDIT：他の人が指摘しているように、定義が再帰的である多くの関数が存在します。 Ackermann function。しかし、これは反復構造を使用して計算することができないことを意味するわけではありません - あなたが完全な操作セットと無制限のメモリを持っている限り。

Answer 7

ずに表現することができないあなたは、再帰なしTuring Machineを定義することができます（右？）だから、再帰はTuring-completeする言語は必要ありません。

Answer 8

Ackermann function answerに応答して、これはコール・スタック・イン・アット・リアルト・スタックのかなりの問題です。これはまた、反復バージョンの1つの利点を示しています。

私のプラットフォーム（Python 3.1rc2/Vista32）では、反復バージョンではack（3,7）= 1021が計算され、再帰バージョンではstackoverflowsが返されます。 NB：別のマシンのPython 2.6.2/Vista64でスタックオーバーフローしなかったため、プラットフォームに依存しているようです。

（これは本当に別のコメントのコメントですコードの書式設定....]）

def ack(m,n): 
    s = [m] 
    while len(s): 
    m = s.pop() 
    if m == 0: 
     n += 1 
    elif n == 0: 
     s.append(m-1) 
     n = 1 
    else: 
     s.append(m-1) 
     s.append(m) 
     n -= 1 
    return n