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:

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:

Zitat von BlackJack

Zitat:

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:

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 :mrgreen: : 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 ( :wall: ) 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. :zwinker:

[marabu]

Hallo BlackJack,

Zitat:

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 :o)

[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 :stupid:

[BlackJack]

Zitat:

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

Zitat:

Zitat von Marabu

Hallo BlackJack,

Zitat:

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 :mrgreen:
(daher hatte ich wohl auch die Idee mit der CPU... sorry wenn ich das jetzt jemandem die Idee geklaut habe. :oops:

[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:

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

[alzaimar]

Wie speichert man den Stack?

[Der_Unwissende]

Ich glaube immernoch, dass du dir gar nicht den ganzen Stack merken musst. Bei einem Bruteforce musst du doch über irgendeine Struktur iterieren (z.B. ein Wörterbuch, ein Eingabealphabet oder eine Zahl oder oder oder). Dahinter steckt doch aber eine Struktur.
O.b.d.A. nehmen wir mal an du benutzt ein Wort. Also musst du dir doch eigentlich nur merken, welches Wort gerade dran ist. Der Nachfolger für dieses Wort dürfte eindeutig sein. Alle Vorgänger scheiden aus, denn sie waren ja falsch. Dann musst du dir nicht die Mühe machen den Stack zu sichern.
Deshalb denke ich aber auch, dass du das ganze gleich iterativ lösen (erspart dir dann die gesamten Rücksprünge). Kann natürlich sein, dass dein Algorithmus nicht Endrekursiv ist (hatten wir ja schon), dann kannst du es nicht so leicht so gestalten. Aber ich denke, du kannst die Rekursion dann auch leicht umwandeln (in Endrekursion) und es dir dann merken. Hängt aber natürlich davon ab, wie dein Algorithmus aussieht.

[alzaimar]

Ist der Algorithmus geheim? Vielleicht können wir ihn ja iterativ umformulieren?

[ripper8472]

bruteforce, also "raufzaehlen" kann man doch ganz einfach fortsetzen. dazu braucht man nur eine increment() funktion, die auf eine "zahl" eben was draufzaehlt. rekursion gibts da nichtmal in der increment() funktion.

[tommie-lie]

Zitat:

Zitat von ripper8472

bruteforce, also "raufzaehlen" kann man doch ganz einfach fortsetzen.

Je nach Angriffsmethode ist BruteForce nicht immer nur stupides hochzählen. Denk' zum Beispiel mal an das Knacken eines Labyrinths per BruteForce, bei dem man das Labyrinth in einzelne Labyrinthe unterteilt und rekursiv den gleichen Algorithmus aufruft, bis man entweder in einer Sackgasse landet oder am Ausgang. In dem Fall könnte ich mir zwar Knotenpunkte merken, an denen ich schon war, aber dadurch wird der Algorithmus ungemein komplizierter, weil ich nicht mehr nach einem einfachen Schema das Labyrinth durchsuchen kann.

[Vjay]

@alzaimar

Ich gebe dir völlig Recht in deiner Behauptung dass jede rekursive Funktion in eine iterative umgewandelt werden könnte - da der Compiler ja nichts anderes macht.

Auch wenn der Bruteforce-Algo sicherlich in eine iterative Funktion umgebaut werden könnte, würde mich trotzdem die ursprüngliche Fragestellung interessieren.

Denn auch wenn man jede nun iterative Funktion mit Unterbrechungs- und Wiedereinstiegsfunktionen versehen könnte, wäre es unter umständen sehr viel einfacher wenn man einen Thread suspenden und seinen gesamten Stack sichern und wiederherstellen könnte. Okay das wird sicher auch alles andere als einfach aber interessieren würde es mich schon sehr. Und wenn hier jemand dafür etwas aus dem Hut zaubern könnte wäre ich davon, auch wenn ich es wahrscheinlich nie verwenden werde, ziemlich begeistert ;).

[alzaimar]

Das wirklich sehr weit ausgeholt mit der Theorie über Transformationen, zurück zum Thema:
Soweit ich das weiss (von Tommie-lie), geht das so nicht, d.h. man kann den Stack zwar sichern, aber wiederherstellen ist nich, das erlaubt XP nicht. Ausser, du schreibst Dir einen Treiber.

[tommie-lie]

Zitat:

Zitat von alzaimar

das erlaubt XP nicht

Genau genommen (und wir wollen ja pingelig sein :zwinker:) erlaubt es der Prozessor nicht, der verweigert nämlich den Zugriff auf die GDT, wenn man selbst nicht im Ring 0 läuft, und ein vernünftiges Betriebssystem würde Anwendungen never ever im Ring 0 laufen lassen (Für Anwendungen gilt allgemein: Ring 3 oder gar nicht :mrgreen:).

[alzaimar]

Zitat:

Zitat von tommie-lie

Zitat:

Zitat von alzaimar

das erlaubt XP nicht

Genau genommen (und wir wollen ja pingelig sein :zwinker:) erlaubt es der Prozessor nicht...im Ring 0 läuft, und ein vernünftiges Betriebssystem ...

Da werd ich pingeligtechnisch noch mal nachhaken: Ist 'Ring 0' eine Eigenschaft eines "vernünftigen Betriebssystems", oder der CPU?

[tommie-lie]

Zitat:

Zitat von alzaimar

Ist 'Ring 0' eine Eigenschaft eines "vernünftigen Betriebssystems", oder der CPU?

Der CPU. Moderne Intel-Prozessoren (IIRC 80286 und aufwärts, vielleicht auch erst ab 80386) haben für ihren Protected Mode sogenannte Ringe, 4 an der Zahl. Ring 0 ist vom dunklen Herrscher über dem Feuerberg geschmiedet worden, deswegen hat der auch die meisten Privilegien. Den dritten Ring bekamen die ollen Zwergenkönige, der hat die wenigsten Privilegien.
Im Protected Mode befinden sich in den Segmentregistern keine echten Adressen mehr, sondern Segmentselektoren, die auf einen Eintrag in der Deskriptortabelle zeigen. So ein Selektor besteht aus dem Index, 'nem Verweis ob es die Local oder die Global Descriptor Table (LDT, GDT) geht, und zwei Bits für das Requested Privilege Level. Ein Programm darf nur auf ein Segment zugreifen, wenn das RPL des Codesegmentes (aktuelles Privilege Level) kleiner oder gleich dem RPL des Zielsegmentes ist. Läuft mein Code im Ring 3 weil das Codesegment ein RPL von 3 hat, dann kann ich nur auf Datensegmente zugreifen, die ebenfalls 3 sind. Läuft mein Code hingegen im Ring 2, darf ich auf Segmente in Ring 2 und 3 zugreifen. In einem Segmentdeskriptor gibt es ebenfalls ein Descriptor Privilege Level, durch das gewährleistet wird, daß wirklich nur Prozesse im richtigen Ring auf einen Deskriptor zugreifen können.
Die gesamte Prüfung rund um Privilege Levels wird von der Adressierungslogik des Prozessors durchgeführt (im Fehlerfalls gibt's deswegen 'ne Hardwareexception (der allseits beliebte Protection Fault oder Schutzverletzung)) und hat mit dem Betriebssystem nichts zu tun.

[Meflin]

Zitat:

Zitat von alzaimar

Ist der Algorithmus geheim? Vielleicht können wir ihn ja iterativ umformulieren?

nein: http://www.delphipraxis.net/internal...ct.php?t=62161

Delphi-Quellcode:

procedure BruteForceFunc(const init, str: string);
  var i: integer;
      npw: string;
  begin
    if slResult.Count >= BatchSize then begin
      if Assigned (KeyList) then KeyList.AddStrings(slResult);
      csThreadCounter.Enter;
      Progress := Progress + slResult.Count;
      csThreadCounter.Leave;
      slResult.Clear;
    end;

    for i := 1 to Length (str) do begin
      npw := init + str[i];
      if Length (npw) >= fStartLength then begin
        slResult.Add(npw);
        ThreadInfo[arrayID].Progress := ThreadInfo[arrayID].Progress + 1;
      end;
      if Length (npw) < fEndLength then BruteForceFunc (npw, str);
    end;
  end;

ist das herzstück

[alzaimar]

Na, super, fast eine Endrekursion.
Einfach einen Stack, bestehend aus 2 Strings erzeugen (Ich hab das als TStringlist gemacht, nicht perfekt, reicht aber).

Am Anfang schiebst Du 'init' und 'str' auf rauf. Anstatt rekursiv aufzurufen, schiebst Du die Parameter, mit der Du dich sonst rekursiv aufrufen würdest, einfach auf den Stack. Ich gehe mal davon aus, das Du das Ergebnis des rekursiven Aufrufes in der For-Schleife nicht benötigst. Ich sehe auch einige globale Variablen, aber das checkst Du bestimmt selbst.

Delphi-Quellcode:

procedure IterativeBruteForceFunc(const init, str: string);
var i: integer;
    npw: string;
    StackedInit, StackedStr : TStringlist;

begin
  StackedInit := TStringList.Create;
  StackedStr := TStringlist.Create;
  StackedInit.Add (init);
  StackedStr.Add (Str);
  While StackedInit.Count > 0 do begin
(****************************************)
    Init := StackedInit [StackedInit.Count -1];
    Str := StackedStr[StackedStr.count - 1];
    StackedInit.Delete (StackedInit.Count - 1);
    StackedStr.Delete (StackedStr.Count - 1);
(****************************************)
    if slResult.Count >= BatchSize then begin
      if Assigned (KeyList) then KeyList.AddStrings(slResult);
      csThreadCounter.Enter;
      Progress := Progress + slResult.Count;
      csThreadCounter.Leave;
      slResult.Clear;
    end;

    for i := 1 to Length (str) do begin
      npw := init + str[i];
      if Length (npw) >= fStartLength then begin
        slResult.Add(npw);
        ThreadInfo[arrayID].Progress := ThreadInfo[arrayID].Progress + 1;
      end;
      if Length (npw) < fEndLength then Begin
(*****************************************)
        StackedInit.Add (Npw); //      BruteForceFunc (npw, str);
        StackedStr.Add (Str);  
(*****************************************)
      end;
    end;
  End;
End;

[dimo]

PS: Habe gerade gesehen, dass diesen Vorschlag schon existiert.

Der Prozeduraufruf wird mit Stack implementiert.
Dies kannst Du auch selber nachmachen - dafür steht die Klasse TStack zur Verfügung. Natürlich ist normalerweise eine rekursive Funktion kürzer und einfacher zu programieren.
Ein schematischer Beispiel, der alle Dateien rekursiv (d.h. auch in Unterverzeichnisse) anzeigt:

Delphi-Quellcode:

procedure recurse_dirs(path : string);
var   sr : TSearchRec;
begin
   if FindFirst(path+PathDelim+'*.*', faAnyFile, sr) = 0 then begin
      repeat
         if (sr.Attr and faDirectory) = faDirectory then begin
            if (sr.Name <> '.') and (sr.Name<>'..') then
               recurse_dirs(path+PathDelim+sr.Name);
         end else begin
            showmessage(path+PathDelim+sr.Name);
         end;
      until FindNext(sr) <> 0;
      FindClose(sr);
   end;
end;

Kann folgendermassen ohne Rekursion geändert werden:

Delphi-Quellcode:

procedure iterate_dirs(startpath : string);
var   sr : TSearchRec;
   stack : TStack;
   path : PAnsiChar;
   subdir : PAnsiChar;
begin
   stack:= TStack.Create;

   path:= StrAlloc(length(startpath)+1);
   StrPCopy(path, startpath);
   stack.Push(path);

   while stack.Count>0 do begin
      path:= stack.pop;
      if FindFirst(path+PathDelim+'*.*', faAnyFile, sr) = 0 then begin
         repeat
            if ((sr.Attr and faDirectory) = faDirectory) then begin
               if (sr.Name <> '.') and (sr.Name<>'..') then begin
                  subdir:= StrAlloc(Length(path+PathDelim+sr.Name)+1);
                  StrPCopy(subdir, (path+PathDelim+sr.Name));
                  stack.push(subdir);
               end;
            end else begin
               showmessage(path+PathDelim+sr.Name);
            end;
         until FindNext(sr) <> 0;
         FindClose(sr);
      end;
      StrDispose(path);
   end;
   stack.Free;
end;

Natürlich ist die Ausgabereihenfolge unterschiedlich, die ist aber bei vielen Aufgaben egal. Hört sich an wie Breiten vs. Tiefensuche ;) Ist es auch dasselbe in dem Fall.

Zustand speichern in diesem Fall wäre einfach den Stack speichern... Das ist das Gute an dieser Methode.
Grüße,
Dimo