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