Welche rekursiven Funktionen können nicht mit Loops umgeschrieben werden?

Question

Soweit ich weiß, können am meisten rekursive Funktionen mit Schleifen umgeschrieben werden. Einige vielleicht härter als andere, aber die meisten von ihnen können neu geschrieben werden.

Unter welchen Bedingungen wird es unmöglich, eine rekursive Funktion mit einer Schleife neu zu schreiben (wenn solche Bedingungen bestehen)?

Answer 1

Wenn Sie eine Funktion rekursiv verwenden, nimmt die Compiler Pflege für Sie von Stack-Management, das ist, was Rekursion möglich macht. Alles, was Sie rekursiv tun können, können Sie tun, indem Sie einen Stack selbst verwalten (für die indirekte Rekursion müssen Sie nur sicherstellen, dass Ihre verschiedenen Funktionen diesen Stack teilen).

Also, nein, es gibt nichts, was mit Rekursion getan werden kann, und das kann nicht mit eine Schleife und ein Stapel getan werden.

Answer 2

Sie können alle als iterative Schleife geschrieben werden (aber einige benötigen möglicherweise noch einen Stack, um den vorherigen Zustand für spätere Iterationen beizubehalten).

Answer 3

Sie können immer eine Schleife verwenden, aber Sie müssen möglicherweise mehr Datenstruktur erstellen (z. B. einen Stapel simulieren).

Answer 4

Es ist nicht so wichtig, dass sie nicht mit Loops implementiert werden können, es ist die Tatsache, dass die Funktionsweise des rekursiven Algorithmus viel klarer und präziser (und in vielen Fällen mathematisch beweisbar) ist richtig.

Viele rekursive Funktionen können als rekursive Endlosschleife geschrieben werden, die zu einer Schleife optimiert werden kann, aber dies hängt sowohl vom Algorithmus als auch von der verwendeten Sprache ab.

Answer 5

Ich weiß nicht, über Beispiele, bei denen rekursive Funktionen können nicht auf eine iterative Version umgewandelt werden, aber unpraktisch oder extrem ineffizient Beispiele sind:

• Baum-Traversal

• schnelle Fourier-

• quicksorts (und einige andere iirc)

Im Grunde alles, wo Sie beginnen müssen, grenzenlose potenzielle Zustände zu verfolgen.

Answer 6

Jede rekursive Funktion kann zur Iteration (in eine Schleife) gemacht werden, aber Sie müssen einen Stack selbst verwenden, um den Status beizubehalten.

Normalerweise Endrekursion ist einfach in eine Schleife zu konvertieren:

A(x) { 
    if x<0 return 0; 
    return something(x) + A(x-1) 
} 

in übersetzt werden kann:

A(x) { 
    temp = 0; 
    for i in 0..x { 
    temp = temp + something(i); 
    } 
    return temp; 
} 

Andere Arten von Rekursion, die in Endrekursion übersetzt werden können, sind auch leicht zu Veränderung. Die anderen erfordern mehr Arbeit.

wie folgt zusammen:

treeSum(tree) { 
    if tree=nil then 0 
    else tree.value + treeSum(tree.left) + treeSum(tree.right); 
} 

Ist das nicht leicht zu übersetzen. Sie können ein Teil der Rekursion entfernen, aber das andere ist nicht ohne eine Struktur möglich, um den Zustand zu halten.

treeSum(tree) { 
    walk = tree; 
    temp = 0; 
    while walk != nil { 
    temp = temp + walk.value + treeSum(walk.right); 
    walk = walk.left; 
    } 
} 

Answer 7

Ein Beispiel, das sehr schwierig sein würde, von rekursiv zu konvertieren wäre zu iterativ die Ackermann function.

Answer 8

Indirekte Rekursion ist immer noch möglich, um in eine nicht-rekursive Schleife zu konvertieren; Beginnen Sie einfach mit einer der Funktionen und verknüpfen Sie die Aufrufe mit den anderen, bis Sie eine direkt rekursive Funktion haben, die dann in eine Schleife umgesetzt werden kann, die eine Stack-Struktur verwendet.

Answer 9

Jede rekursive Funktion kann mit einer einzigen Schleife implementiert werden.

Denken Sie nur, was ein Prozessor tut, führt er Anweisungen in einer einzigen Schleife aus.

Answer 10

In SICP fordern die Autoren den Leser heraus, eine rein iterative Methode zur Implementierung des Problems "Zähländerung" (here's an example eins vom Projekt Euler) zu entwickeln.

Aber die strikte Antwort auf Ihre Frage wurde bereits gegeben - Schleifen und Stapel können jede Rekursion implementieren.