Von Rekursiv zu Iterativ


starbug

Erfahrenes Mitglied
#1
Hallo Leute,

habe mal wieder eine Frage. Wie kann man am betsen vorgehen wenn man eine rekursive Funktion in eine iterative Funktion umwandeln möchte? Habe hier ein Beispiel für eine rekursive Funktion:

Code:
public static int sum(int n)
    {
        int result;
        if(n==0)
        {
            result = 0;
        }else
        {
            result = sum(n-1)+(n*n);
        }
        
        return result;
    }
Hier mal eine Lösung von mir zur iterativen Funktion, welche aber Falsch ist, da ich die variable result doch noch irgendwie speichern muss oder?

Code:
 public static int sumIterativ(int n)
    {
        int result =0;
        while(n>0)
        {
            result = n+(n*n);
            n--;
        }
       
        return result;
    }
Bin für jede Antwort dankbar
 
#2
Hi Starbug,
eine allgemeine Lösung für das Umwandeln einer rekursiven Methode in eine iterative gibt es nicht; das ist in jedem Fall besonders - in diesem Fall muss dir klar sein, was genau zurückgegeben werden soll: die Summe aller Quadrate von 1 bis n. Dabei wird (rekursiv) zuerst die Summe von n^2 + sum (n-1) zurückgegeben, bis n = 1 ist; diese Summe ist dannd as Ergebnis. Deine iterative Methode ist fast richtig; du rechnest zwar für jedes einzelne n das Quadrat aus, lässt es aber aus, dies auch mit den schon vorher berechneten Quadraten zu summieren. Du müsstest also aus
Java:
result = n+(n*n)
dieses hier machen:
Java:
result = result + (n*n)
MfG
 

genodeftest

Erfahrenes Mitglied
#3
Hi
allgemein wandelt man rekursive Funktionen in iterative F. um, indem man sich die Parameter ansieht, mit denen die rekursive F. sich selbst aufruft. Diese Parameter folgen meist einem Schema, in deinem Fall wird die Variable 'n' in jedem Schritt um 1 reduziert. Andere übliche Schemata sind:
– Konstante zur Zahl addieren, subtrahieren
– Zahl multiplizieren
– bei baumähnlichen Strukturen: Eine Ebene nach oben/unten gehen
Wenn du das Schema erkannt hast, kannst du direkt aus dem Aufruf der F. in sich selbst eine Schleifenvariable herauslesen und aus dem Schema z.B. einen Inkrement oder Dekrement machen.

In deinem Beispiel wäre das:
Java:
public static int sumIterativ(int n){
     int result = 0;
     while(n>0){
          result += n+(n*n);
          n--;
     }
     return result;
}
bis auf eine Kleinigkeit hat dein Code also gestimmt. Du hast nur vergessen, in Zeile 6 das vorherige Ergebnis dazu zu addieren.