Rekursion zu Iteration

[gordon freeman]

Hi Leute,
ich hab schon gegoogelt und die Forensuche bemüht, aber eventuell mit den falsche Suchbegriffen. Ich suche nach einem Verfahren, wie ich jegliche Rekursion iterativ mache. Dabei soll es egal sein, welchen Grad die Rekursion hat. Es geht in meinem Beispiel um eine dreigradige Rekursion. Gibt es nun ein allgemeines Schema, mit dem ich eine Rekursion zu einer Iteration mache, oder geht das nur mit jede Menge Gehirnschmalz?

mfg, tia, Martin

[DGL-luke]

Naja, die gelehrten Köpfe streiten sich doch immer noch, ob beweisbar jede Rekursion zu einer Iteration gemacht werden kann.

Also würd ich schon sagen, jede menge Hirnschmalz. Aber ich glaube, du solltest sie dir zumindest iterativ nachbilden können, indem du einen eigenen Stack anlegst und dann das ganze in eine while-schleife verpackst. Zumindest so vom Ansatz her :stupid: müsste das gehen, wenn du eine weitere Rekursion dadurch anstößt, dass du den stack mit entsprechenden daten pushst und ein Break; setzt. Am nede der rekursion, sprich am ende des blockes innerhalb der while-schleife, wird der stack dann abgebaut.

[bttb930]

naja, der vorschlag mit dem stack würde bedeuten, dass du eine iteration so baust, dass sie die nachteile der rekursion nachbildet. also nichts gewonnen, nur verloren.

[gordon freeman]

Also gibt es da kein einfaches Verfahren? Schade. :(
Dann werd ich wohl mal meine kleinen grauen Zellen anstrengen müssen. Danke für die schnellen Antworten.

[Sidorion]

Imho ist man sich wohl mittlerweile einig, dass man
a) jede Rekursion auch iterativ darstellen kann und umgekehrt (wobei der Aufwand oft in keinem Verhältnis steht) und
b) es keine allgemeingültige Methode, gibt nach der dies geschehen kann.
Will heissen: Möglich isses, muss aber für jeden konkreten Fall betrachtet werden.

[shmia]

Es gibt allerdings immer die Möglichkeit, die Endrekursion zu vermeiden.
Beispiel:

Delphi-Quellcode:

procedure MachwasRekursiv(parameter);
begin
   BerechneSchritt1;
   if rekusionsbedingung then
      MachwasRekursiv(neueparameter);
end;

dies kann so übersetzt werden:

Delphi-Quellcode:

procedure MachwasIterativ(parameter);
begin
   repeat
      BerechneSchritt1;
      parameter := neueparameter;
   until not rekusionsbedingung;
end;

Bei der Beseitigung der Endrekursion setzt man also einfach die (Funktions-)Parameter auf die neuen Wert und steigt in der Funktion oben wieder ein.
Hier ist durchaus der GOTO-Befehl erlaubt, da er unnötiges Zuweisen der neuen Parameter vermeidet.

Delphi-Quellcode:

procedure MachwasIterativ(parameter);
Label start;
begin
   start:
   BerechneSchritt1;
   if rekursionsbedingung then
   begin
      parameter := neueparameter;
      Goto Start;
   end;
end;

Wenn es sich nicht um eine Endrekursion handelt, kann dieses Verfahren nicht funktionieren:

Delphi-Quellcode:

procedure MachwasRekursiv(parameter);
begin
   BerechneSchritt1;
   if rekusionsbedingung then
      MachwasRekursiv(neueparameter);
   BerechneSchritt2;  // wegen dieser Anweisung liegt KEINE Endrekursion vor
end;

[MaBuSE]

Zitat:

Zitat von shmia

Bei der Beseitigung der Endrekursion setzt man also einfach die (Funktions-)Parameter auf die neuen Wert und steigt in der Funktion oben wieder ein.
Hier ist durchaus der GOTO-Befehl erlaubt, da er unnötiges Zuweisen der neuen Parameter vermeidet.

Delphi-Quellcode:

procedure MachwasIterativ(parameter);
Label start;
begin
   start:
   BerechneSchritt1;
   if rekursionsbedingung then
   begin
      parameter := neueparameter;
      Goto Start;
   end;
end;

Das sehe ich nicht so.
Goto hat in Delphi / Pascal eigentlich nix zu suchen.

Delphi-Quellcode:

repeat
  BerechneSchrit1;
  if RekursionsBedingung then Parameter := NeuerParameter;
until not RekursionsBedingung;

oder zur Not:

Delphi-Quellcode:

var weiter: Boolean;
...
repeat
  BerechneSchrit1;
  weiter := KomplizierteRekursionsBedingung; 
  if weiter then  Parameter := NeuerParameter;
until not weiter;

[gordon freeman]

Hm, das sind ja jetzt alles allgemeine Beispiele zur 1fachen Rekursion, gibt es dass auch zur 3fachen Rekursion und dann so übersetzt in die Iteration?

[MaBuSE]

Was verstehst Du denn unter 3fach Rekursion?

[gordon freeman]

Sorry, hab mich falsch ausgedrückt, ich meinte 3 gradige Rekursion, also:

Delphi-Quellcode:

procedure recursion(n: paramter);
begin
if not (Endbedingung) then 
  begin
   recursion(modify1(n));
   recursion(modify2(n));
   recursion(modify3(n));
  end;
end;

EDIT: Das mit der Rekursion ist aber auch vertrackt :wall:

[MaBuSE]

Zitat:

Zitat von gordon freeman

Sorry, hab mich falsch ausgedrückt, ich meinte 3 gradige Rekursion, also:

Delphi-Quellcode:

procedure recursion(n: paramter);
begin
  recurse1(modify1(n));
  recurse2(modify2(n));
  recurse3(modify3(n));
end;

Sorry, aber das sind ja nur 3 Aufrufe hintereinander.

Die Procedure Recursion ist also iterativ!
(Eine Funktion ist erst dann rekursiv, wenn sie sich selbst aufruft, nicht weil sie recursion heißt. ;-))

Wenn recurse1 bis recurse3 jeweils nur eine einfache EndRekursion sind und modifyX keine Rekursive Funktion, dann brauchst Du doch nur die 3 rekursiven Procedure auf Iteration umzustellen.

Fertig

[MaBuSE]

sorry... (hatte Zitat statt Edit gedrückt :duck: )

[gordon freeman]

Großer Fehler, hab mich total verhauen mit der Rekursion und hab's oben geändert.

[Der_Unwissende]

Hi,
nimm einfach die Ackermann-Funktion. Die ist gut rekursiv und nicht uninteressant (gab hier mal die Diskussion ob diese iterativ dargestellt werden kann). Die erfüllt (imho) alle Schwierigkeiten, die man so an eine rekursive Funktion stellen kann und es gab wenn ich mich richtig erinnere auch eine iterative Lösung. Weiß leider nicht mehr wer die gefunden hatte (ich weiß noch dass ich deren Existenz anzweifelte). Da wurde dann auch darüber diskuttiert, ob denn jede rekursive Funktion auch iterativ gelöst werden könnte und zumindest für alle Endlichen Fälle müsste das möglich sein. Wie schon gesagt wurde, es gibt leider kein Verfahren, dass immer und für jeden Fall funktioniert.

Gruß Der Unwissende

[alzaimar]

Zitat:

Zitat von Der_Unwissende

Hi,
nimm einfach die Ackermann-Funktion. Die ist gut rekursiv und nicht uninteressant (gab hier mal die Diskussion ob diese iterativ dargestellt werden kann). Die erfüllt (imho) alle Schwierigkeiten, die man so an eine rekursive Funktion stellen kann und es gab wenn ich mich richtig erinnere auch eine iterative Lösung. Weiß leider nicht mehr wer die gefunden hatte

Ich war's :stupid: , nämlich her

[Der_Unwissende]

[OT]

Zitat:

Zitat von alzaimar

Ich war's :stupid: , nämlich her

Hatte ich mir doch fast gedacht :wink:
Beim Beweis mit der CPU wußte ich noch, dass der von dir kam, bei dem anderen war ich mir nicht 100%ig sicher (wußte aber auch noch, dass du da einige gute Argumente hattest und wohl immer noch hast).

Gruß Der Unwissende
[/genug OT]