Rekursion Summe

[glitsch]

Hi zusammen,
Rekursive Algorithmen wollen bei mir noch nicht ganz rein. Keine Ahnung ob mir jemand entsprechende Lektüre oder Videos empfehlen kann? Auf jeden Fall krieg ich selbst einfache Algos nicht gebacken:

public static int rek(int n) {
		int s = 5;
		if (s<n) {
		System.out.println(s + " " + n);
		s = rek(n-1)+n;
		System.out.println(s + " " + n);
		}
		return s;
}
Aufruf mit: rek(10);

Mein Algo soll einfach mal nur ohne die Sonderfälle abzudecken rekursiv von hinten aufsummieren. Eigentlich in meinem Kopf eine logische Sache. Nimm das Ende und das zweite letzte Element und addiere diese zusammen. Ich hab mir mal entsprechende prints eingebaut, um das ganze besser zu verstehen. Wieso ist mein s nach dem ersten Rekursionsdurchlauf direkt 11? Ich rechne da: n-1+(altes)n, das müssten dann doch 19 sein? :bahnhof:

Irgendwo steckt der Knoten.

 

[SlaterB]

die Rekursion geht zunächst immer runter, bis n == s == 5 ist, dann wird 5 zurückgegeben,
in der vorherigen Stufe war n == 6, zusammen 11, die hohen Zahlen kommen erst zum Schluss wieder dran

gerade mit der Ausgabe eigentlich zu erkennen

 

[pappawinni]

rek(10) .. if trifft zu.. und fordert s = rek(10-1)+10, d.h das fordert die Berechnug von
rek(9) .. if trifft zu.. und fordert s = rek(9-1)+9, d.h. das fordert die Berechnung von
rek(8) .. if trifft zu.. und fordert s = rek(8-1)+8, d.h. das fordert die Berechnung von
rek(7) .. if trifft zu.. und fordert s = rek(7-1)+7, d.h. das fordert die Berechnung von
rek(6) .. if trifft zu.. und fordert s = rek(6-1)+6, d.h. das fordert die Berechnung von
rek(5) .. if triff NICHT zu, es wird erst jetzt
5 zurückgegeben, was dann
5+6 = 11 an den vorigen Aufruf zurück gibt, was dann
11+7 = 18 an den vorigen Aufruf zurück gibt, der seinerseits
18+8 = 26 an den vorigen Aufruf zurück gibt, der seinerseits
26+9 = 35 an den vorigen Aufruf zurück gibt, der seinerseits
35+10 = 45 an den vorigen Aufruf zurück gibt, was schliesslich
die Ausgangsfrage beantworten sollte.
rek(10) = 45

Die Rekursion löst sich also von der Abbruchbedingung ausgehend rückwärts auf.

 

[Fab1]

OT: Denk dir nichts, jetzt beschäftige ich mich wirklich schon ne Weile mit Java, aber an der Rekursion verzweifle ich immer wieder. Gut, ich weiche ihr auch immer aus, aber mei...

Ich hab mir hier mal eine Vorlesung zur Programmierung angeschaut in der auch die Rekursion gut erklärt wurde. Leider habe ich das Video nicht mehr gefunden, da die Seite umgebaut wurde (denke ich), aber evtl. wirst du ja fündig. Online-Video-Vorlesungen Informatik

 

[Landei]

Rekursion ist eng verwandt mit einem induktiven Beweis. Wie dort gibt es einen "Basisfall", und einen "Schritt" von einer Stufe zur nächsten. Wenn beides korrekt ist, funktioniert sowohl der Beweis wie auch die Rekursion. Der "Trick" ist also, sich von der Korrektheit der aktuellen Stufe zu überzeugen, und davon auszugehen, dass der rekursive Aufruf schon "das Richtige" tut.

Schreiben wir einmal eine rekursive Funktion zur Berechnung des Quadrats einer Zahl. Was ist der Basisfall? Nun, geeignet wäre hier 0² = 0 (negative Zahlen klammern wir hier einmal aus). Angenommen, wir würden bereits das Quadrat von (n-1) kennen, wieviel größer wäre dann das das Quadrat von n? Hier hilft der binomische Satz: (n-1)² = n² - 2n + 1, also n² = (n-1)² + 2n - 1. Damit sind wir wirklich schon fertig, wir können das ganz genau so hinschreiben:

public static int square(int n) {
   if (n == 0) { //Basisfall
      return 0;
   } else { //Schritt
      return square(n-1) + 2*n - 1; 
   } 
}

Du brauchst eigentlich nicht darüber nachzudenken, was square(n-1) eigentlich tut - wenn square(n) funktioniert, wird es auch funktionieren, denn es ist ja die gleiche Methode. Spielen wir es trotzdem durch: Für n = 0 haben wir den Basisfall, bekommen also 0 zurück. Für n = 1 erhalten wir square(0) + 2*1 - 1 = 0 + 2 - 1 = 1. In Ordnung. Für n = 2 haben wir square(1) + 2*2 - 1 = 1 + 4 - 1 = 4. Und so weiter. Aber man muss dieser "Abwärtsspirale" mental gar nicht folgen, es reicht, wenn die beiden Elemente "Basisfall" und "Schritt" wirklich korrekt sind, dann funktioniert das ganze Ding.

Eine iterative Version der "Abwärtsspirale", die sich die rekursiven Aufrufe spart, und stattdessen die "Buchhaltung" für n und das Resultat selbst übernimmt, würde so aussehen:

public static int square(int n) {
   int result = 0;
   while (n > 0) { 
      result += 2*n - 1; 
      n--;
   }
   return result; 
}

 

[hüteüberhüte]

Schön erklärt, obwohl ich jetzt durch die Formeln nicht so durchgestiegen bin.

Nehmen wir einmal die Fakultät:

    public static long fak(int i) {
        if (i <= 1) {
            return 1;
        }
        return i * fak(i - 1);
    }

    public static void main(String[] args) {
        System.out.println(fak(5));
    }

Für i=1 ist 1 das richtige Ergebnis.

Für von n-1 nach n müsste (n-1)*fak(n-2)*n richtig sein. (?)

Grüße

 

[pappawinni]

Schöne Erklärung Landei.
Rekursionen beschränken sich halt vielleicht nicht nur auf Mathematik.
Ich denke, dass die wichtigste Erkenntnis wäre, dass sich das Ganze erst an der Abbruchbedingung (Basisfall) aufzulösen beginnt.
Rekursion bedeutet gewissermassen, bildlich gesprochen, dass auf eine erste Frage mit einer Frage geantwortet wird, die wieder eine Frage aufwirft usw., bis irgendwann keine Frage, sondern eine Antwort (Basisfall) geliefert wird, mit deren Hilfe es dann systematisch gelingt nacheinander die vorangegangenen Fragen zu beantworten.
Oder....die Rekursion bläht sich auf, bis sie an die Nadelspitze stösst, die das Ding zum Platzen bringt.

 

[hüteüberhüte]

Obwohl es Quatsch ist, so eine Methode zu schreiben, weil 60 Fakultät bereits so viel wie alle Atome im Universum ist. ^^

 

[bERt0r]

Also bei mir kommt folgendes raus:

5 10
5 9
5 8
5 7
5 6
11 6
18 7
26 8
35 9
45 10

Kann es sein, dass du nur glaubst dass 11 am anfang steht weil du die console nicht raufgescrollt hast?

 

[tröööt]

@hüte
deinen code mal mit BigInteger geschrieben ergibt bei mir für 60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000
und ich glaube da trifft deine aussage nicht ganz zu wenn man sich mal nur alleine vorstellt aus wie vielen atomen EIN mensch besteht ... und davon gibt es gut 7 milliarden auf diesem planeten ...
wenn man sich den spaß macht könnte man , wenn man "den durchschnittsmenschen" nimmt , auch errechenen wie viel atome die erde gesamt hat , also mit allen lebewesen und atmospähre und so weiter ...
und wenn man dann weiterspinnt das unsere erde alleine in unserem sonnensystem nur einen winzigsten bruchteil der gesamtemasse außmacht ... und alleine unsere sonne mehr als 99,999% unseres sonnensystems hat ... und man sich nur mal die aberwitzige anzahl an möglichen sonnensystemen alleine unserer milchstraße ansieht ... ich glaube dann ist man schon weit über diese zahl hinaus ... und wirklich weiterspinnen mit den unzähligen galaxien die es gibt braucht man dann wohl nicht mehr ...

(würde gern mal ne quelle für diese aussage haben)

 

[SlaterB]

8320987112741390144276341183223364380754172606361245952449277696409600000000000000
> 10^82

Anzahl der Atome
"Dies sagt uns, daß die Anzahl der Atome im Universum etwa in der Größenordnung 10^78 ist."

edit:
weitere Quellen gehen aber auch höher, in der Kürze soeben auch bis zu 10^89 gelesen

 

[hüteüberhüte]

@hüte
deinen code mal mit BigInteger geschrieben ergibt bei mir für 60! = 8320987112741390144276341183223364380754172606361245952449277696409600000000000000
und ich glaube da trifft deine aussage nicht ganz zu wenn man sich mal nur alleine vorstellt aus wie vielen atomen EIN mensch besteht ... und davon gibt es gut 7 milliarden auf diesem planeten ...
wenn man sich den spaß macht könnte man , wenn man "den durchschnittsmenschen" nimmt , auch errechenen wie viel atome die erde gesamt hat , also mit allen lebewesen und atmospähre und so weiter ...
und wenn man dann weiterspinnt das unsere erde alleine in unserem sonnensystem nur einen winzigsten bruchteil der gesamtemasse außmacht ... und alleine unsere sonne mehr als 99,999% unseres sonnensystems hat ... und man sich nur mal die aberwitzige anzahl an möglichen sonnensystemen alleine unserer milchstraße ansieht ... ich glaube dann ist man schon weit über diese zahl hinaus ... und wirklich weiterspinnen mit den unzähligen galaxien die es gibt braucht man dann wohl nicht mehr ...

(würde gern mal ne quelle für diese aussage haben)

Wie Slater schon schrieb: Anzahl der Atome

Und wenn man sich die Größe verschiedener "Objekte" klar machen will: The Scale of the Universe 2

Genau genommen reicht auch schon 59 Fakultät. Mit irgendetwas, das mehr Atome als das Universum hat, wird man wahrscheinlich nie rechnen müssen...

Die Fakultät ist also eine sehr schnell wachsende Funktion, das wollte ich damit ausdrücken.

Grüße!

 

[glitsch]

OK, musste das Beispiel nochmals raus greifen. Wenn jetzt n = Obergrenze wäre, wie kann ich dann am einfachsten sagen in der Rekursion, ABER nicht mehr 10 dazuaddieren? Ich könnte in der Bedingungsprüfung (s+1) setzen. Aber ich find den Algorithmus für meine Aufgabe noch etwas holprig.

Kann mir jemand sagen, wie ich das besser machen kann? :idea:

 public static int rek(int n) {
		int s = 5;
		if ((s+1)<n) {
		s = rek(n-1)+n;
		}
		return s;
	}

Das Ganze fängt bei 5 an. Das ist quasi die Untergrenze.

 

[DrZoidberg]

Erstmal musst du genau wissen was die Methode eigentlich zurückliefern soll.
In diesem Fall soll sum(n) die Summe aller Zahlen von 1 bis n liefern.
Die Summe aller Zahlen von 1 bis n ist natürlich die Summe aller Zahlen von 1 bis n-1 plus n.

Versuch erstmal die rekursive Methode ohne den Basisfall aufzuschreiben.

[Java]public static int sum(int n) {
return sum(n-1)+n;
}[/Java]

Das sieht schon mal ganz gut aus. Allerdings gibt das natürlich eine unendliche Rekursion bzw. einen Stack Overflow.
Deshalb muss da jetzt noch der Basisfall rein.

[Java]public static int sum(int n) {
if(n == 0) return 0;
else return sum(n-1)+n;
}[/Java]

Wenn ich dich richtig verstanden habe, willst du jetzt aber die Summe von 1 bis n plus 5.
Kein Problem.

[Java]public static int sum(int n) {
if(n == 0) return 5;
else return sum(n-1)+n;
}[/Java]

 

[Spacerat]

Wenn ich dich richtig verstanden habe, willst du jetzt aber die Summe von 1 bis n plus 5.
Kein Problem.

...und wenn ich das richtig verstanden habe, soll 5 die Untergrenze sein:
[Java]public static int sum(int n) {
if(n <= 5) return 15;
else return sum(n-1)+n;
}[/Java]
Und wenn die Obergrenze nicht hinzuaddiert werden soll:
[Java]public static int sum(int n) {
n--;
if(n <= 5) return 15;
else return sum(n)+n;
}[/Java]
Beides verfälscht aber die Werte unter 5, sodass
[Java]public static int sum(int n) {
n--
if(n <= 0) return 0;
else return sum(n)+n;
}[/Java]
letztendlich korrekt wäre.
[EDIT][OT]Ich hab' das grad' mit der Anzahl an Atomen im Universum gelesen... Woher wisst ihr eigentlich, wieviele abermillarden Galaxien jenen Lebewesen bekannt, welche uns nicht bekannt sind? Die Anzahl der Atome des uns bekannten Universums mag ja nur ca. 10^100 sein, aber auf den unbekannten "Rest" :lol: trifft das definitiv nicht zu, da sind's nicht mehr als unbedeutende 8 (frag' mich allerdings, warum man diese 8 ständig auf die Seite legt. ???:L).[/OT][/EDIT]

 

[glitsch]

Danke an alle für die guten Antworten. Man muss halt nur kapieren, daß zuerst die ganzen Methoden hintereinander aufgerufen werden OHNE das etwas berechnet wird und erst am Schluss wieder rückwärts die Werte an die vorherigen Methodenaufrufe übergeben werden. Rekursion ist quasi nicht nur einfach "rückwärts" rechnen, sondern im Prinzip ein rückwärts Aufrufen der Methoden und dann ein vorwärts rechnen durch rückwärts übergebende Werte. Ok, klingt paradox, aber so kann ichs mir merken... ^^