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.
So einfach ist es leider nicht - bspw. sind nicht Schleifen wirklich das Problem, sondern aufeinanderfolgende Befehle. Aber über die rein theoretische Definition von TMs lässt sich das ganze einfacher in rekursive Ausdrücke überführen.
Doch ist jede Rekursion auch als Iteration abbildbar? Dazu fehlen mir die Kenntnisse. Ist das schon bewiesen worden?
In den 30ern von Alonzo Church, durch die Turingvollständigkeit von Lambdaausdrücken. Eine etwas einfachere und verständlichere Variante wäre die iterative Traversierung von Rekursionsbäumen. Im Endeffekt arbeitet deine CPU auch nur iterativ, und simuliert lediglich rekursive Aufrufe.
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.
Inwiefern eine Umsetzung unbefriedigend oder zufriedenstellend ist, hängt in erster Linie von den Möglichkeiten und Erwartungen ab. Allerdings ist das dann nicht eine "verkappte Rekursion", sondern eine möglichst allgemein anwendbare Überführung eines rekursiven Ausdrucks in eine iterative Form.
Ich habe auf die Schnelle keine Quelle gefunden, die es explizit auf Iteration zurückführt, aber es gibt Funktionen, die insbesondere im Compilerbau Kopfschmerzen machen, nämlich nicht-primitiv-rekursive Funktionen (Ackermannfunktion, Busy Beaver, Sudanfunktion, etc.).
Ich meine mich zu erinnern, dass man die nicht einfach auf eine iterative Variante zurückführen kann.
Nichtprimitiv-rekursive Funktionen bieten nur dann Probleme, wenn der Compiler versucht, diese zu optimieren. Ansonsten ist die Überführung in eine iterative Variante für den Compiler nicht sonderlich schwierig. Auch wenns widersprüchlich klingen mag, aber der CALL-Befehl auf CPU-Ebene ist rein iterativ.
Was den genannten Busy Beaver betrifft: Der ist gar nicht berechenbar, somit gibts weder eine iterative, noch ne rekursive Beschreibung dieser Funktion.
greetz
Mike