Die rekursiven Funktionen nicht neu geschrieben werden, mit Schleifen?
Soweit ich weiß, die meisten rekursiven Funktionen umgeschrieben werden kann unter Verwendung von Schleifen. Einige vielleicht schwerer als andere, aber die meisten von Ihnen geschrieben werden kann.
Unter welchen Bedingungen macht es unmöglich, so zu umschreiben, dass eine rekursive Funktion mit einer Schleife (wenn solche Bedingungen existieren)?
- Ich vermute, dass du tatsächlich meinst, die können nicht umgeschrieben werden, ohne irgendeine form von Stapel, ist das so?
- Eigentlich keine. Ich meine, wenn es völlig unmöglich zu umschreiben, dass es mit einer Schleife. Ich denke an die indirekte Rekursion als Beispiel.
- secweb.cs.odu.edu/~zeil/cs361/Website/website/Vorlesungen/...
Du musst angemeldet sein, um einen Kommentar abzugeben.
Wenn eine Funktion rekursiv, der compiler kümmert sich um stack-management für Sie, das ist, was macht der Rekursion möglich. Alles, was Sie tun können, rekursiv, die Sie tun können, durch die Verwaltung ein stack sich selbst (für indirekte Rekursion, Sie müssen nur sicherstellen, dass Sie Ihre verschiedenen Funktionen zu teilen, dass der Stapel).
So, Nein, es gibt nichts, was getan werden kann, mit Rekursion und das kann nicht getan werden, mit einer Schleife und einem Stapel.
Jede rekursive Funktion kann vorgenommen werden, um iterativ (in einer Schleife), aber Sie müssen verwenden einen stack, sich selbst zu halten den Staat.
Normalerweise, tail recursion ist einfach zu konvertieren in eine Schleife:
Übersetzt werden kann:
Andere Arten der Rekursion, die übersetzt werden kann in die tail-Rekursion sind auch leicht zu ändern. Die anderen erfordern mehr Arbeit.
Folgende:
Ist nicht ganz leicht zu übersetzen. Sie können entfernen Sie ein Stück der Rekursion, der andere aber ist nicht möglich ohne eine Struktur zum halten der Staat.
Jede rekursive Funktion implementiert werden kann mit einer einzigen Schleife.
Nur denken was für ein Prozessor hat, er führt die Anweisungen in einer einzelnen Schleife.
Ich weiß nicht, über Beispiele, in denen rekursive Funktionen, die nicht konvertiert werden, um eine iterative version, aber unpraktisch oder extrem ineffizient Beispiele sind:
tree traversal
fast-Fourier -
quicksorts (und einige andere, iirc)
Im Grunde nichts, wo Sie beginnen, verfolgen Sie grenzenloses potential Staaten.
Es ist nicht so sehr eine Sache, die Sie können nicht implementiert werden unter Verwendung von Schleifen, es ist die Tatsache, dass die Art und Weise der rekursive Algorithmus arbeitet, ist es viel klarer und präziser (und in vielen Fällen mathematisch beweisbar), dass eine Funktion korrekt ist.
Viele rekursive Funktionen geschrieben werden können, werden tail-rekursive Schleife, die optimiert werden können, um eine Schleife, aber dies ist abhängig von sowohl der Algorithmus und die verwendete Sprache.
Sie alle geschrieben werden kann als eine iterative Schleife (aber einige vielleicht noch ein Stapel vorherigen Zustand für spätere Iterationen).
Einem Beispiel, das würde äußerst schwierig sein, zu konvertieren von rekursiv auf iterativ wäre die Ackermann-Funktion.
Indirekte Rekursion ist immer noch möglich, zu konvertieren, um eine nicht-rekursive Schleife; einfach starten Sie mit einer der Funktionen, und inline die Anrufe zu den anderen, bis Sie eine direkt rekursive Funktion, die dann übersetzt werden, um eine Schleife, die verwendet eine stack-Struktur.
In SICP, die Autoren der Herausforderung, den Leser auf eine rein iterative Methode, die die Umsetzung der 'counting-ändern" - problem (hier ist ein Beispiel eine vom Projekt Euler).
Aber die strenge Antwort auf deine Frage schon gegeben, - Schleifen und-stacks implementieren kann jede Rekursion.
Können Sie immer eine Schleife verwenden, aber Sie müssen möglicherweise mehr Daten-Struktur (z.B. Simulation eines stack).