Hilfe bei Rekursion!! Prüfungsfrage

[drdragon]

Guten Morgen,
ich schreibe am Dienstag eine Prüfung, in der auch das rekursive Programmieren eine Rolle spielt. Hier hab ich jedoch noch ein Problem:

Aufgabe: Schreibe folgende Summenfunktion sum(n)=0+1+2+...+(n-2)+(n-1)+n in einer rekursiven Methode.

Lösung von einem wissenschaftlichen Mitarbeiter:

public int sum(int n) {
if (n==0) return 0;
else return n + sum(n-1);
}

Wenn ich nun aber mal als Beispiel die Zahl 3 nehme, bekomme ich aus der Methode doch das Ergebnis 6.
Allerdings: sum(3) = 0+1+2+3+(3-3)+(3-2)+(3-1)+3 = 12

Wo liegt mein Denkfehler??
Bitte um Hilfe.. wäre wichtig für mich!

Danke!!

 

[Rainbow]

Hi,
also wenn wir mal dein Beispiel n = 3 nehmen dann läuft das so ab:

sum(3) = 3 + sum(2) = 3 + (2 + sum(1)) = 3 + 2 + (1 + sum(0)) = 3 + 2 + 1 + 0 = 6

verstehst du?

 

[Hrtgpdh]

Dein Denkfehler liegt daran, das du von 0 ausgehst, diese Rekursion läuft vom n-ten Element bis null --> dementsprechend bei drei Elementen 3+(3-1)+(2-1)+(1-1). Das Ergebnis ist dann auch 6

 

[drdragon]

Ok, super. Danke für die schnellen Antworten!

Heißt mal rein mathematisch lässt man bei sum(n)=0+1+2+...+(n-2)+(n-1)+n den Teil "0+1+2+.." weg und berechnet nur den hinteren Teil?

 

[Landei]

Man läßt überhaupt nichts weg, man zählt einfach rückwärts: 3 + (3-1) + (3-2) + (3-3)

Rückwärts zu zählen ist ein netter Trick, denn man weiß ja, dass man bei 0 fertig ist und aufhören muss. Wenn du unbedingt von "vorne" anfangen willst, geht das auch, aber dann du brauchst eine zusätzliche Methode, die sich dein n "merkt" (weil man das ja für eine Abbruchbedingung braucht):

public int sum(int n) {
   return sumHelper(0,n);
}

private int sumHelper(int k, int n) {
   if(k == n)  return k;
   else return k + sumHelper(k+1,n);
}

Die erste Lösung ist wesentlich eleganter.

Du musst dich mental vom "Schleifendenken" lösen, das ganze ähnelt eher einem "Beweis mit vollständiger Induktion":
Wie berechne ich eine Summe von 0 bis n (Rückwärtsversion)?
- Wenn n gleich 0 ist, ist die Summe 0
- Wenn nicht, dann benötige ich die Summe von 0 bis (n-1), dann addiere ich n dazu und bin fertig.

Wie berechne ich eine Summe von 0 bis n (Vorwärtsversion)?
Schreibe eine Hilfsfunktion, die die Summe von k bis n berechnet, lasse diese die Summe von 0 bis n berechnen.
Hilfsfunktion, um die Summe von k bis n zu berechnen:
- Wenn k = n ist, ist die Summe k
- Wenn nicht, dann benötige ich die Summe von k+1 bis n, dann addiere ich k dazu und bin fertig.

 

[drdragon]

Ok, nun habe ich es endgültig kapiert!! :toll:

Danke nochmal an alle!!!!

 

[objcler]

Ich will auch so einfache Aufgaben haben