Theorie: Rekursive Funktion Abbrechen und Fortsetzen

[Meflin]

Aloha!

Ich stehe momentan vor folgendem Problem: ich habe eine rekursive Funktion, die auch wunderbar funktioniert. Da aber das, was sie tut, mit unter recht zeitaufwendig ist, wäre es ganz nützlich, den "Status" der Funktion abspeichern zu können und zu einem beliebigen Zeitpunkt, auch nach Beenden des ausführenden Programmes, wieder fortsetzen könnte.

Allerdings habe ich absolut keine Idee wie sich soetwas lösen liese.

Anregungen sind deshalb *sehr* erbeten

[BlackJack]

vielleicht könnten dir Threads hier weiterhelfen; damit kann man dann zwar nicht so ohne weiteres die procedure erst beim nächsten programmstart weiter laufen lassen (was auch ziemlich sehr schwer werden dürfte), aber die procedure unterbrechen und nachher weiterlaufen lassen (oder auch andere prioritäten festlegen) sollte mit Threads eigentlich recht gut gehen.

[Der_Unwissende]

Hi,

um was für eine Art von Rekursion handelt es sich denn? Ich denke es ist nicht möglich pauschal zu sagen wie man so etwas implementieren kann ohne die Art der Rekursion zu kennen.
Ist dein Algorithmus einfach Endrekursiv, gäbe es ja schon die möglichkeit ihn iterativ rechnen zu lassen, was natürlich Zwischenzustände sehr viel einfacher macht, wenn du aber z.B. die Ackermann-Funktion berechnen möchtest, glaube ich dürfte es sehr viel schwerer sein, hierfür eine Lösung zu finden

[Meflin]

@BlackJack: die Funktion einfach zu pausieren ist kein Problem - läuft bereits in einem Thread

@Unwissender: es handelt sich um eine Brute Force Funktion (genauer gesagt um die in meiner Komponente, siehe Open Source Forum). Meinst du mit Endrekursiv, dass ich vorher weiß, wie lange die Funktion läuft? das wäre wohl der Fall...

Im großen und ganzen dachte ich viel eher an sowas wie den Stack abzuspeichern und wiederherzustellen, das erscheint mir, wenn möglich, am einfachsten, wenn es auch kompliziert sein dürfte.

[Der_Unwissende]

Nein, endrekursion ist, hm moment *malWeitAusholt*

Also wenn du etwas rekursiv berechnest, was genau auf einem weiterem (rekursivem) Funktionsaufruf basiert (z.B. Fakultät), dann kannst du diesen Aufruf häufig auch endrekursiv gestallten. Das heißt, du merkst dir in einem Wert, den man Akkumulator nennt, einfach dein Zwischenergebnis. Für die Fakultät kannst du also anfangen und merkst dir in einer Variablen, die Fakultät n (für die ersten n Schritte) und im Schritt (n+1) multiplizierst du n mit (n+1) und speicherst das als dein neues n. Dann musst du natürlich noch wissen wieviele Schritte du schon gemacht hast. Sagen wir du willst die Fakultät von k berechnen, dann hast du ja irgendwann k Schritte gemacht. Endrekursiv heißt dann, dass du einfach fertig bist. In dem n dass du nach k Schritten hast, steht ja deine Lösung. Du brauchst also nicht zurückzuspringen in den vorherigen Aufruf (CODE folgt).
Bei nicht endrekursivem vorgehen rechnest du halt so, dass Fakultät (n = n * Fakultät n-1) ist d.h. wenn du Fakultät n-1 kennst, musst du den Wert noch mal benutzen und mit n berechnen. Du knallst dir also schnell den Stack voll mit Aufrufen, die auf ein Ergebnis warten müssen.

Bei einem Brute-Force iterierst du ja eigentlich über eine gewisse Menge. Da wüßte ich jetzt ehrlich gesagt nicht warum es rekursiv laufen müsste (i.d.R. schlechter als iterativ). Du kannst es wahrscheinlich leicht in eine Iteration umwandeln und dir dann einfach merken, wo du zuletzt warst. So dass du deine Untere und Obere Grenze als Parameter übergibst und dann kannst du beim pausieren einfach diese beiden Grenzen speichern. Der restliche Code könnte dann konstant sein, für alle variablen Teile gilt hingegen, dass man sie als Parameter übergibt und dann halt abspeichern und laden können sollte (was dann sicher kein Prob ist?)

[alzaimar]

Der Nick von 'Der_Unwissende' passt nicht zu seinem Statement! Du hast völlig Recht, ich füge nur noch hinzu:

Jeder rekursive Algorithmus lässt sich in einen Iterativen umwandeln!

[Der_Unwissende]

Bist du dir sicher, dass sich jeder umwandeln lies? Also ich weiß noch, dass der Aufwand natürlich unterschiedlich groß ist, endrekursive sind schon (fast komplett) iterativ, andere überführt man in Endrekursion, aber galt dass nicht nur für primitiv Rekursive Funktionen? Dachte eigentlich das Ackermann dann definitiv nicht iterativ lösbar war (siehst du, wohl unwissend).
Aber egal, ist ja vollkommen Off Topic, oder?

[BlackJack]

Zitat von Der_Unwissende:

Dachte eigentlich das Ackermann dann definitiv nicht iterativ lösbar war (siehst du, wohl unwissend).
Aber egal, ist ja vollkommen Off Topic, oder?

dachte ich eigentlich genauso auch immer, aber letztens hat mich jemand eines besseren belehrt. der meinte dann halt das iteration und rekursion grundsätzlich zwei ineinander überführbare lösungswege liefern.

und wenn du es mal so siehst: die CPU macht ja auch bei der doppelt-rekursiven Ackermann-Funktion alles iterativ hintereinander

[Eichhoernchen]

Zitat von BlackJack:

Zitat von Der_Unwissende:

Dachte eigentlich das Ackermann dann definitiv nicht iterativ lösbar war (siehst du, wohl unwissend).
Aber egal, ist ja vollkommen Off Topic, oder?

dachte ich eigentlich genauso auch immer, aber letztens hat mich jemand eines besseren belehrt. der meinte dann halt das iteration und rekursion grundsätzlich zwei ineinander überführbare lösungswege liefern.

und wenn du es mal so siehst: die CPU macht ja auch bei der doppelt-rekursiven Ackermann-Funktion alles iterativ hintereinander

womit hat er das begründet? also ich bin eigentlich auch der Meinung, dass nicht jedes rekursive iterativ lösbar ist.

[alzaimar]

Zitat von Eichhoernchen:

also ich bin eigentlich auch der Meinung, dass nicht jedes rekursive iterativ lösbar ist.

Must du auch nicht, ist aber so : Erstens (laut BlackJack) wg. der CPU, die ja nur einen Zähler verwaltet (program counter). Zweitens kannst du ja den Stack mit einer Liste und den rekursiven Aufruf mit einem Goto ( ) simulieren und drittens kann man das beweisen. Wie, weiss ich aber nicht. Die ersten beiden Punkte dürften aber ausreichen.

Mein Beweis:
Behauptung: Jeder rekursive Algorithmus lässt sich in einen iterativen Algorithmus überführen.
Beweis durch Widerspruch: Angenommen, es gäbe einen rekursiven Algorithmus, der *nicht* in einen Iterativen überführt werden kann. Den könntest Du dann auch nicht in einer Programmiersprache codieren, weil ja ein Compiler jede rekursive Routine in eine Iterative überführt (nämlich Maschinencode).
Da nun aber jeder Algorithmus in einer Programmiersprache kodiert werden kann, ist die Annahme ('Es gibt einen ...') falsch, also die Behauptung richtig.

Die Frage ist nun verlagert: "Kann JEDER Algorithmus in einer Programmiersprache kodiert werden?" Meine Antwort: Hängt vom Programmierer ab.