Ich hab' heute nicht so die Zeit, mich da hinein zu vertiefen. Allerdings bin ich mir nicht sicher, ob der Ansatz überhaupt zum Erfolg führt.
Theoretisch kann man ja erst einmal so vorgehen, dass man den CPU-Stack durch einen eigenen Stack ersetzt und statt eines rekursiven Selbstaufrufs die aktuellen Parameter auf diesen Stack legt, durch die neuen ersetzt und einfach einen neuen Schleifendurchlauf macht. Die Funktion ruft sich nicht mehr selbst auf, ergo keine Rekursion.
Allerdings ändert dies ja eigentlich nichts an der Art und Weise, wie der Algorithmus arbeitet (bzw. funktioniert bzw. definiert ist) - unabhängig von der benutzten Programmiersprache werden zur Berechnung des Ergebnisses andere eigene Funktionsergebnisse benutzt.
Ich denke mal, einen solchen Beweis muss man auf einer anderen Ebene führen.
Im Wiki hab' ich unter
Rekursion noch das hier gefunden:
Zitat:
Ein Spezialfall der Rekursion ist die primitive Rekursion, die stets durch eine Iteration ersetzt werden kann. Bei einer solchen Rekursion enthält der Aufruf-Baum keine Verzweigungen, das heißt er ist eigentlich eine Aufruf-Kette: das ist immer dann der Fall, wenn eine rekursive Funktion sich selbst jeweils nur einmal aufruft, insbesondere am Anfang (Head Recursion, siehe Infiniter Regress) oder nur am Ende (Tail Recursion oder Endrekursion) der Funktion. Umgekehrt kann jede Iteration durch eine primitive Rekursion ersetzt werden, ohne dass sich dabei die Komplexität des Algorithmus ändert.
Jetzt muss ich wieder den weltlichen Dingen zuwenden (aka "arbeiten") ... muss bis Morgen noch eine dicke PHP-Anwendung vorstellungsreif hinbekommen ...