ich muss ein Java-Programm schreiben, das die Funktion sum implementiert.
Mein Code:
package sum;
public class Sum {
static int n = 4;
public static int sum(int n){
if(n==0){
return 0;
}
return sum(n-1) + n;
}
public static void main(String[] args){
int a = sum(n);
System.out.println("The sum is: " + a);
}
}
Der Code funktioniert zwar, aber ich verstehe nicht warum ich bei “sum(n-1)” noch + n rechnen muss. Sum-1 ist ja der rekursive Aufruf.
Wenn man jetzt bei return sum(n-1) + n; angekommen ist, dann dürfte das +n doch gar nicht mehr ausgeführt werden, weil man davor schon
zurück zum Anfang der Methode gesprungen ist, oder?
Vielen Dank im Voraus.
LG
Doch + n wird ausgeführt, weil du mit sum(n - 1) nicht an den Anfang der Methode springst, sondern die Methode nochmals aufrufst. Hier mal ein beispiel mit n = 4, dass das ganze vllt etwas verdeutlicht:
Wenn du das +n weglässt, erhältst du (egal für welches Argument) am Ende 0 zurück. Rekursion ist nichts “magisches”, irgendwo muss auch dort die “Arbeit” (hier: das Aufsummieren) getan werden, genauso wie bei der iterativen Lösung. Wie das in diesem Fall aussieht, hat ja mein Vorgänger schön verdeutlicht.
if (n <= 1)
return 2;
return sum(n - 1) + sum(n - 2);
}```
(Oder in einer Zeile mit ? : )
Für
```System.out.println(sum(4));```
wird sogar das obige Ergebnis ausgegeben.
Du musst dir vorstellen:
Da geht links ein Baum auf (der nach unten wächst) und da geht rechts ein Baum auf.
4
2 3
0 1 1 2
2 2 2 0 1
2+2+2+2+2
Parameter haben einen Wert, die werden an den Methodenaufruf kopiert, die werden verändert und als Parameter eines neuen Methodenaufrufs kopiert usw. usf., bis endekriterium.
Do you understand (me)?
Wie @Landei schrieb würde ohne das +n das Ergebnis 0 ergeben, da dann dein Programm folgendes machen würde:
Es wird aufgerufen und ruft sich selber mit -1 auf solange es nicht 0 ist (das ist deine Abbruch Bedingung)
Irgendwann erreichen wir die Abbruch Bedingung (wir sind bei 0)
Nun geben wir immer ein Ergebnis zurück, an dieser stelle 0
Dieses Ergebnis wird nun in der Aufrufenden Funktion (was ja dieselbe Funktion war) weiterverwendet return sum(n-1); somit geben wir direkt das Ergebnis zurück was wiederum 0 ist
Das geht nun solange bis wir am Aufruf sind und 0 als Ergebnis erhalten.
Das ist jedoch nicht gewünscht, deswegen wird dafür das +n benötigt, da dann nach dem man aus dem rekursiven Aufruf zurück kommt noch n dazu zählt (sich aufsummiert)
Somit sieht es bei der Zeile return sum(n-1) + n; nun so aus, das wir 0 zurück geliefert haben, +1 rechnen und somit 1 zurück liefern, in der Ebene (Aufruf vorher) rechnen wir nun 1+2 was 3 ergibt,…
Siehe auch http://de.wikipedia.org/wiki/Rekursion