Ich verstehe die Rekursion noch nicht richtig

[Matze]

Hi zusammen!

Ich habe am Dienstag eine Klausur und verstehe die Rekursion noch nicht so richtig.


Ich habe mit eine kleine Aufgabe ausgedacht und möchte folgendes berechnen:

1² + 2² + 3² + ... + n²

Iterativ habe ich das so gelöst:

Delphi-Quellcode:

function TForm1.Iterativ(n: integer): integer;
var i: integer;
begin
  Result := 0;

  for i := 1 to n do
    Result := Result + sqr(i);
end;

Nach ewigem Rumprobieren habe ich's rekursiv auch hinbekommen:

Delphi-Quellcode:

function TForm1.Rekursiv(n: integer): integer;
begin
  if n > 0 then
  begin
    Summe := Summe + sqr(n);
    Rekursiv(n-1);
  end;
  Result := SUmme;
end;

Die Variable "Summe" habe ich global deklariert, da ich nicht wusste, wie ich das nur lokal mache, bzw. ob das nur lokal überhaupt geht.



Mir fällt das noch recht schwer, die Rekursion.

Kann mir jemand Tipps geben, wie ich, gerade bei Aufgaben dieser Art, rekursiv vorgehen muss?
Ich wäre euch sehr dankbar!

[Phoenix]

Wirklich rekursiv wäre folgendes:

Delphi-Quellcode:

function TForm1.Rekursiv(n: integer): integer;
begin
   if n = 1 then
      result := 1
   else
      result := sqr(n) + rekursiv(n-1);
end;

[Phoenix]

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.

[Matze]

Wow, das ist ja super erklärt!

Vielen Dank Phoenix.
Jetzt habe ich es endlich kappiert.

[Matze]

Da mir Phoenix so gut geholfen hat, habe ich gedacht, ich programmiere mal schnell eine Potenzfunktion.

Soweit ist das auch ganz gut gelungen, nur ist es jetzt so, dass ich eine Variable global deklarieren möchte, was meinem Lehrer vielleicht nicht so gefällt

So habe ich es probiert:

Delphi-Quellcode:

function TForm1.Rekursiv(n, x: integer): integer;  //x^n
begin
  if n = 1 then Result := x else
  begin
    Wert := Wert * x;
    Result := x * Rekursiv(n - 1, x);
  end;
end;

"Wert" ist global deklariert.

Geht es auch nur mit lokalen Variablen?

[Seniman]

Hallo Matze,

deine Rekursive function berechnet die Potenz gleich zweimal. Das ist unnötig. Lass einfach die Zeile mit dem "Wert" weg.
Dann kannst du die Funktion mit z.B.
Wert:= Rekursiv(2,4); aufrufen.

Grüße
Seniman

[Matze]

Danke, aber irgendwie klappt es dann bei mir nicht mehr

[Seniman]

Hallo Matze,

ich habe es mit der folgenden Funktion hinbekommen und die Unterscheidet sich ja nicht wirklich von deiner. Vielleicht liegt der Fehler woander.

Delphi-Quellcode:

function Rekursiv(n,x: Integer): Integer;
begin
  if n=1 then
    Result:= x
  else
    Result:=Rekursiv(n-1,x)*x;
end;

Grüße
Seniman

[Matze]

Cool, vielen Dank!

Ich denke irgendwie immer zu umständlich.
Es ist ja gar nicht so kompliziert, wie ich gedacht habe!