Rekursion vs. Iteration

[Delphi-Laie]

Zitat von JasonDX:

Zitat von Delphi-Laie:

1. Jedes Element enthält sein eigenes Abbild in der jeweils 1. Subebene nur einmal. So etwas ist z.B. bei der rekursiven Fakultät oder - im materiellen Bereich - bei den russischen Puppen namens Matrjoschka der Fall. Ich bleibe dabei, daß eine solche Rekursion nur eine „Lightversion“ ist, da sie letztlich mit der Iteration konformläuft.

Was genau meinst du mit "konformlaufen"? Dass sich die Rekursion auf einen iterativen Ablauf zurückführen lässt?

Zumindest die, die in Internetamateurenzyklopädie sicher aus gutem Grundes als „iterative“ Rekursion bezeichnet wird.

Zitat von JasonDX:

Dann ist jede Rekursion eine "Lightversion".

Das ist die entscheidende Frage. Jede Iteration läßt sich als Rekursion darstellen, denn letztlich rufen - in gewisser Weise - sich Schleifen auch nur selbst immer wieder auf.

Doch ist jede Rekursion auch als Iteration abbildbar? Dazu fehlen mir die Kenntnisse. Ist das schon bewiesen worden? In Robert Sedgewicks Standardwerk z.B. stand zur Quicksort, daß sich das nur unbefriedigend als Iteration darstellen/umsetzen läßt. Während der Implementation wurde mir rasch klar, daß mit der dort vorgestellten Quelltext letztlich nur die Stackhandhabung emuliert/simuliert wird, es also eine verkappte Rekursion ist.

Sollte die letzte Frage tatsächlich bejaht werden können, bliebe auf jeden Fall der Vorteil der kurzen, übersichtlichen Problem(lösungs)beschreibung sowie der Quelltexte mit gleichen Eigenschaften, zudem gut wart- und portierbarer Quelltexte.

Edit: Weiter oben schriebst Du, daß es laut „theoretischen Beweisen“ (Anmerkung: Derlei Beweise sind immer theoretisch) möglich sei. Das überlas ich zunächst.