AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Rekursion zu Iteration

Ein Thema von gordon freeman · begonnen am 13. Nov 2006 · letzter Beitrag vom 14. Nov 2006
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von gordon freeman
gordon freeman

Registriert seit: 28. Jun 2003
Ort: Gelsenkirchen
337 Beiträge
 
Delphi 2005 Personal
 
#1

Rekursion zu Iteration

  Alt 13. Nov 2006, 14:25
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
  Mit Zitat antworten Zitat
Benutzerbild von DGL-luke
DGL-luke

Registriert seit: 1. Apr 2005
Ort: Bad Tölz
4.149 Beiträge
 
Delphi 2006 Professional
 
#2

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 14:38
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.
Lukas Erlacher
Suche Grafiktablett. Spenden/Gebrauchtangebote willkommen.
Gotteskrieger gesucht!
For it is the chief characteristic of the religion of science that it works. - Isaac Asimov, Foundation I, Buch 1
  Mit Zitat antworten Zitat
bttb930

Registriert seit: 6. Okt 2003
372 Beiträge
 
#3

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 14:41
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.
  Mit Zitat antworten Zitat
Benutzerbild von gordon freeman
gordon freeman

Registriert seit: 28. Jun 2003
Ort: Gelsenkirchen
337 Beiträge
 
Delphi 2005 Personal
 
#4

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 16:55
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.
  Mit Zitat antworten Zitat
Sidorion

Registriert seit: 23. Jun 2005
403 Beiträge
 
#5

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 16:56
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.
Manchmal sehen Dinge, die wie Dinge aussehen wollen mehr wie Dinge aus, als Dinge
<Esmerelda Wetterwachs>
  Mit Zitat antworten Zitat
shmia

Registriert seit: 2. Mär 2004
5.508 Beiträge
 
Delphi 5 Professional
 
#6

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 17:12
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;
Andreas
  Mit Zitat antworten Zitat
Benutzerbild von MaBuSE
MaBuSE

Registriert seit: 23. Sep 2002
Ort: Frankfurt am Main (in der Nähe)
1.837 Beiträge
 
Delphi 10 Seattle Enterprise
 
#7

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 17:25
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;
(°¿°) MaBuSE - proud to be a DP member
(°¿°) MaBuSE - proud to be a "Rüsselmops" ;-)
  Mit Zitat antworten Zitat
Benutzerbild von gordon freeman
gordon freeman

Registriert seit: 28. Jun 2003
Ort: Gelsenkirchen
337 Beiträge
 
Delphi 2005 Personal
 
#8

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 17:30
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?
  Mit Zitat antworten Zitat
Benutzerbild von MaBuSE
MaBuSE

Registriert seit: 23. Sep 2002
Ort: Frankfurt am Main (in der Nähe)
1.837 Beiträge
 
Delphi 10 Seattle Enterprise
 
#9

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 17:51
Was verstehst Du denn unter 3fach Rekursion?
(°¿°) MaBuSE - proud to be a DP member
(°¿°) MaBuSE - proud to be a "Rüsselmops" ;-)
  Mit Zitat antworten Zitat
Benutzerbild von gordon freeman
gordon freeman

Registriert seit: 28. Jun 2003
Ort: Gelsenkirchen
337 Beiträge
 
Delphi 2005 Personal
 
#10

Re: Rekursion zu Iteration

  Alt 13. Nov 2006, 18:05
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
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 12:02 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz