Einzelnen Beitrag anzeigen

Benutzerbild von Phoenix
Phoenix
(Moderator)

Registriert seit: 25. Jun 2002
Ort: Hausach
7.639 Beiträge
 
#3

Re: Ich verstehe die Rekursion noch nicht richtig

  Alt 16. Jan 2004, 15:19
Ein bisschen zur Theorie:

Rekursion fängt man meistens von hinten an:

In Deinem Fall (1² + 2² + 3² + ... + n²) also mit n. Das Ergebnis dieser Funktion ist also:
Code:
n² + (n-1)² + (n-2)² + ... + 1²
Für sich genommen ist also das Ergbnis der Funktion für jedes n:
Code:
n² + (summer aller weiteren (n-1)² bis hin zu eins).
Damit wären wir beim Code:
Delphi-Quellcode:
function recurse(n: integer):integer;
begin
   if n = 1 then
      result := 1
   else
      result := sqr(n) + recurse(n-1);
end;
Was macht das Ding also?
Es nimmt n² und addiert mit dem Ergebnis von sich selber mit (n-1). Die funktion ruft sich also so lange selber auf (der erste Aufruf wartet immer noch auf das Ergbenis!) bis n = 1 ist. Hier stoppt die Rekursion (da konstant 1 zurückgeliefert wird): der letzte Aufruf erhält sein Ergebnis.
Der rechnet nun 2 + 1 und liefert das Ergebnis an den nächste wartenden aufruf. Bis hin zum ersten, der nun sein endgültiges Ergebnis zurückliefern kann.

(Edit zur Veranschaulichung:
Code:
recurse(5) -->
5² + recurse(4) {4² + recurse(3) {3² + recurse(2) { 2² + recurse(1) {1}}}}
(/edit)

Hier sieht man auch den Nachteil von Rekursion:
Wird die Methode zu oft aufgerufen, läuft irgendwann einmal der Stack voll.
Sebastian Gingter
Phoenix - 不死鳥, Microsoft MVP, Rettungshundeführer
Über mich: Sebastian Gingter @ Thinktecture Mein Blog: https://gingter.org
  Mit Zitat antworten Zitat