Theorie: Rekursive Funktion Abbrechen und Fortsetzen

[marabu]

Hallo BlackJack,

Zitat von BlackJack:

dachte ich eigentlich genauso auch immer, aber letztens hat mich jemand eines besseren belehrt.

war das etwa hier?

Grüße vom marabu

PS: schöner Beweis, alzaimar.

[Flocke]

[OT]

Folgende Funktion (absichtlich nicht optimiert) berechnet die Summe von 1 bis N (N ist das Argument).

Code:

asm_proc:
    mov  edx, 0
    cmp  eax, 0
    jle  done
    push eax
    dec  eax
    call asm_proc
    pop  edx
    add  edx, eax
done:
    mov  eax, edx
    ret

Natürlich kann man das auch iterativ lösen, aaaaber:

1. Ist es Maschinensprache? ja (nein, Assembler, aber ihr wisst schon...)
2. Ist es rekursiv? ja

Somit ist diese Annahme hinfällig:

Zitat:

weil ja ein Compiler jede rekursive Routine in eine Iterative überführt (nämlich Maschinencode).

Maschinencode kann auch rekursiv sein!

Wichtig: ich sage damit ja nicht, dass die Behauptung an sich falsch ist.

[runger]

Hallo,

Zitat:

weil ja ein Compiler jede rekursive Routine in eine Iterative überführt (nämlich Maschinencode).

das ist schlichtweg falsch. Es ist völlig unerheblich ob ich rekursiv in Maschinensprache oder in einer Hochsprache programmiere.
Rekursiv heisst doch nichts anderes als dass der Code in einer Schleife immer wieder durchlaufen wird, das einzige was sich ändert sind die Daten auf dem Stack.

Rainer

[alzaimar]

@Flocke: Der Beweis von mir ist dann nicht richtig formuliert. Ich will ja gerade darauf hinaus, das eine sich selbst aufrufende Routine iterativ abgearbeitet wird.

@runge: Es ist eine andere Sichtweise. Wenn ich Rekursion so definiere:" Eine Routine ist rekursiv gdw. sie sich selbst aufruft", dann gibt es rekursiven Maschinencode. Wenn man es streng sieht, so wie Du, gibt es gar keine Rekursion, oder wie würdest Du sie definieren?

Sagen wir es so: "Ein Compiler überführt jeden rekursiven Algorithmus in einen Maschinencode, der per se iterativ ausgeführt wird, denn der in der CPU ablaufende Microcode ist streng iterativ."

Das kommt hin, oder?

[Flocke]

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 ...

[Der_Unwissende]

Zitat:

Ein Spezialfall der Rekursion ist die primitive Rekursion

Schön, damit wären wir wieder am Ausgangspunkt (glaube ich). Denn was ist die Alternative zu primitiver Rekursion? Richtig, nü-rekursive Funktionen, ergo Ackermann.
Eigentlich glaube ich ist es auch vollkommen egal ob man nun jede rekursive Funktion überführen kann oder nicht, ein Beweis dürfte für die Ackermann so gut wie unmöglich sein. Immerhin ist es nicht mal klar, ob diese Funktion immer terminiert. Also hier kann man sogar das ganze auf ihre Endlichkeit beschränken, das Ergebnis sollte für jede Eingabe immer gleich sein.

Was die Argumentation mit der CPU angeht, damit es ein Beweis wäre, müsste natürlich auch erstmal gezeigt werden, dass
a) die CPU nur iterativ arbeitet (ok, nehmen wir doch mal an dass das trivial gegeben wäre) aber auch
b) sich jeder Rekursive Algorithmus durch eine CPU berechnen lässt.
Das sollte schon deutlich schwerer sein. Ich schmeiß jetzt mal (ohne weiter drüber nachzudenken) Halteproblem eines Rekursiv laufenden Programms in den Raum. Na gut, ist glaube ich ein sehr schlechtes Beispiel, immerhin Semi-Entscheidbar (oder?)
Aber wenn es einen nicht entscheidbaren Algorithmus gibt der rekursiv läuft (und bei überabzählbar vielen wäre das wohl keine Kunst), dann wäre dies schon mal ein Problem das keine CPU berechnen kann.
Kommen wir also zur Einschränkung, dass eine CPU alle berechenbaren Probleme iterativ lösen könnte. Und damit auch schon zu den Grenzen einer realen CPU und künstlichen Modellen wie den Primitiv-Rekursiven Funktionen, dem Lambda-Kalkül und natürlich der guten alten Turing-Maschine (und wohl weiteren). Die sind wohl ohne Frage mächtiger als jede CPU es je sein wird (sorry an alle die eh nur noch Bahnhof verstehen).
Kurzum, es wird wohl nichtmal jede entscheidbare Funktion durch eine CPU berechenbar sein (ok, es gibt nur abzählbar viele, aber die Menge dieser Funktionen dürfte sich wohl bijektiv auf die Menge der natürlichen Zahlen abbilden lassen). Also gibt es abzählbar viele Probleme (wohl auch unendlich), für die dieser Beweis nicht gilt. Damit stellt sich die Frage ob es irgendeinen Sinn macht so zu argumentieren (fand die Argumentation gar nicht schlecht, bitte nicht falsch verstehen). Die Verallgemeinerung dass jeder Rekursive Algorithmus sich iterativ berechnen lässt (implizit vorrausgesetzt er ist berechenbar) kann nicht auf Eigenschaften einer CPU zurückgeführt werden.
Eine andere Sache ist, wen interessiert eigentlich genau ob sich nun jede Funktion von rekursiv nach iterativ überführen lässt? Denke mal hier ist es mehr als out of topic, aber sicherlich eine interessante (vielleicht schon lange gelöste) Frage der Theoretischen Informatik.
By the way, mich würde die Antwort interessieren (nicht der Beweis )

[Meflin]

*hüstel* ich unterbreche euch ja nur ungern... nur geht das langsam *etwas* am thema vorbei. warum ich meine brute force funktion rekusrsiv gelöst habe? ich wüsste nicht, wie ich das verwendete verfahren ohne rekursion lösen sollte... und eigentlich sehe ih auch keinen bedarf, denn es funzt so einwandfrei.

deswegen möchte ich dem thema doch dezent einen stups in die eigentliche richtung geben, nämlich wie man sowas speicherbar machen kann

[BlackJack]

Zitat von Der_Unwissende:

Die Verallgemeinerung dass jeder Rekursive Algorithmus sich iterativ berechnen lässt (implizit vorrausgesetzt er ist berechenbar) kann nicht auf Eigenschaften einer CPU zurückgeführt werden.

naja so theoretisch war das mit meinem Einwurf mit der CPU auch nicht gemeint. Das sollte mehr so als Anstoß dienen, damit sich Leute schnell mal klar machen können "Hey, egal wie ekelhaft-komplizierte Rekursionen ich hier programmiere(!), letztendlich arbeitet die CPU die doch eh iterativ ab!"
nichtsdestotrotz {1 wort? 3 wörter?} fand ich deine erklärungen aber sehr informativ und auch einleuchtend.

Zitat von Marabu:

Hallo BlackJack,

Zitat von BlackJack:

dachte ich eigentlich genauso auch immer, aber letztens hat mich jemand eines besseren belehrt.

war das etwa hier?

Grüße vom marabu

hmm ja das kann gut sein
(daher hatte ich wohl auch die Idee mit der CPU... sorry wenn ich das jetzt jemandem die Idee geklaut habe.

[brechi]

Ich weiß nicht obs noch net gesagt wurde aber:

man kann eine rekursive funktion schon speichern und später fortsetzen wenn man keine windows spezifischen sachen wie z.b. handles etc. darin benutzt.

Man muss es nur im thread auslagern und den stack sichern, denk mal ich kann dafür gleich mal nen beispiel schreiben.
Sieht dazu CreateThread / GetThreadContext / SetThreadContext

[Meflin]

Zitat von brechi:

Ich weiß nicht obs noch net gesagt wurde aber:

man kann eine rekursive funktion schon speichern und später fortsetzen wenn man keine windows spezifischen sachen wie z.b. handles etc. darin benutzt.

Man muss es nur im thread auslagern und den stack sichern, denk mal ich kann dafür gleich mal nen beispiel schreiben.
Sieht dazu CreateThread / GetThreadContext / SetThreadContext

jepp, das mit dem Stack war mein Vorschlag. aber ihc wüsste bis jetzt nicht wie...