Rekursion und Iteration

[Nobody]

Es wird immer wieder gefragt, was rekursion ist und ob es dafür tutorials gibt.
kurz und einfach gesagt: NEIN

rekursion:
eine methode ruft sich selbst auf. jede rekursive lösung, lässt sich auch iterativ lösen.

iteration:
innerhalb der methode erfolgt ein linearer ablauf.

nun fragen sich sicherlich einige: warum dann überhaupt rekursion?
in der regel sind die rekursiven lösungen (sofern sie überhaupt sinnvoll sind) einfacher zu programmieren und benötigen weniger quelltext. allerdings sind diese langsamer, da die gesamte methoden neu in den stack geladen werden, als komplett neuer speicherbereich (der alte teil bleibt erhalten).

klingt vielleicht ein wenig komisch, aber hier mal ein beispiel, dass den aufruf verdeutlicht und die einfachere variante zeigt:

Bsp: Fakultät

//der aufruf erfolgt von einer anderen methode und erhält das ergebniss zurück
public int Fak(int n){
  if(n>1){
    return(n * Fak(n-1)); //Hier ist der rekursive aufruf der methode
  }
  else{
     return(1);
  }
}

das ganze ist nun sehr einfach und übersichtlich. auch eine simulation ist recht einfach (kann bei anderen beispielen deutlich komplexer sein).

//hier das ganze iterativ
public int Fak(int n){
int erg=1;
  for(int i=2;i<=n;i++){
    erg=erg*i;
  }
return erg;

hier wird der unterschied noch nicht ganz so deutlich. bei komplexeren problemen, wird dies meist deutlicher (wer ein besseres leicht verständliches hat schicke ne pn an mich, dann mach ich sie anstelle dessen rein, nur fällt mir grad keins ein, dass leicht verständlich ist).

 

[bygones]

jede rekursive lösung, lässt sich auch iterativ lösen.

Da würde ich mal dagegen wetten - wenn ich so an manche Algorithmen - Vorlesung denke :wink:

 

[Nobody]

nun teilweise wären sie dann abartig komplex, aber gehen würde es. teilweise muss dann auch eine andere logik zugrunde gelegt werden

 

[bygones]

meine wette läuft ja darauf hinaus, dass ich dann jemanden sehe will der das programmiert :lol: :wink:

 

[Ebenius]

Nun, ob es endlich lösbare rekursive Lösungswege gibt, die iterativ nicht umgesetzt werden können, weiß ich nicht. Definitiv gibt es unendliche rekursive Lösungswege, die nicht iterativ vorhanden sind (ich denke da in Richtung PI, Quadratur des Kreises, ...).

GRINS