Stack Overflow

[evilhomer]

Hi!

Ich bin gerade dabei einen Algorithmus zu erstellen, der beliebig viele der ersten Primzahlen rekursiv berechnet. Für mich erscheint der Code logisch, Abbruchbedingungen sind auch definiert, trotzdem beklagt sich Delphi über einen StackOverflow. Der Code sieht folgendermaßen aus:

Delphi-Quellcode:

procedure TForm1.Prim_re(n,i:integer);

begin
if (n < limit) then begin
       if (i<=1) then List2.Items.Add(IntToStr(n))
       else
         if (n mod i) <> 0 then  Prim_re(n,i-1);
       end;
  Prim_re(n+1,n);
end;

Die Variable limit ist die Obergrenze, bis zu der Primzahlen gesucht und in der List2 angezeigt werden sollen. n steht für die aktuelle Zahl, die auf Teilbarkeit untersucht wird und i ist sozusagen eine Laufvariable.
An sich ist der Code also nicht allzu schwer zu durchblicken.
Ich hoffe dass irgendjemand mir helfen kann, bzw. weiß wo hier der Fehler liegen könnte?

Gruß und danke im Voraus

[mkinzler]

Lass dir mal n und i kontiniurlich anzeigen

[evilhomer]

Okay, wenn ich mir den Stack anschaue, dann zeigt er mir:

TForm1.Prim_re(2,???)
TForm1.Prim_re(3,???)
TForm1.Prim_re(4,???)
TForm1.Prim_re(5,???)

usw...
bloß, wie kommt es dazu?

[mkinzler]

Nirgends musst du selber machen

[evilhomer]

Gut, wenn ich den erneuten Aufruf

Delphi-Quellcode:

Prim_re(n+1,n);

auskommentiere, dann funktioniert es zumindest, aber das liefert mir natürlich nur eine Zahl, nicht die ganze Liste mit 100,200, wie vielen auch immer. Gibt es da einen Weg, die Funktion ohne Error aufzurufen? (Immerhin muss es rekursiv bleiben..)

[FAlter]

Hi,

der Code ist sehr eigenartig, hier einmal anders formatiert:

Delphi-Quellcode:

procedure TForm1.Prim_re(n,i:integer);
begin
  if (n < limit) then 
  begin
    if (i<=1) then 
      List2.Items.Add(IntToStr(n))
    else
    if (n mod i) <> 0 then
      Prim_re(n,i-1);
  end;

  Prim_re(n+1,n);
end;

Ich hoffe, jetzt wird die dein Fehler deutlich. Prim_re(n+1, n) wird IMMER aufgerufen, unabhängig davon, om n < limit.

Mfg
FAlter

[NormanNG]

Hi,

ich formatier deinen Quelltext mal etwas um:

Delphi-Quellcode:

procedure TForm1.Prim_re(n,i:integer);
begin
  if (n < limit) then 
  begin
    if (i<=1) then 
      List2.Items.Add(IntToStr(n))
    else
      if (n mod i) <> 0 then 
        Prim_re(n,i-1);
  end;
  Prim_re(n+1,n);
end;

Jetzt siehtst du vielleicht, dass das mit der Abbruchbedingung noch nicht so ganz stimmt:
Egal, mit welchem N/I die Prozedur aufgerufen wird, sie sich ruft zuletzt immer wieder selbst auf.
Also nichts mit "Abbruch" ...

[edit]Upps, roter Kasten?[/edit]

[shmia]

Ich denke mal, der Fehler ist durch deine schlampige Einrückung entstanden.
Hier dein Code nach Borland Style Guide formatiert:

Delphi-Quellcode:

procedure TForm1.Prim_re(n,i:integer); 
begin 
  if n < limit then
  begin 
    if i <= 1 then 
      List2.Items.Add(IntToStr(n)) 
    else if (n mod i) <> 0 then
      Prim_re(n,i-1); 
  end;  // <== dieses end kommt zu früh
  Prim_re(n+1,n);   // <<== diese Zeile muss VOR das end
end;

[evilhomer]

Okay, das Problem hat sich nun erledigt. Der StackOverflow war ja schon beseitigt, und dass die Prozedur sich nur 1mal aufgerufen hat lag am "else if" statt "if"..
Wer den Code mal benötigen sollte, so funktioniert es bei mir:

Delphi-Quellcode:

procedure TForm1.Prim_re(n,i:integer);
var prim:boolean;

begin
  if n < limit then
  begin
    if i = 1 then List2.Items.Add(IntToStr(n));
    if (n mod i) = 0 then Prim_re(n+1,n)
    else Prim_re(n,i-1);
  end;
end;

Danke für eure Hilfe!

[evilhomer]

Sorry, so ganz ist das Problem immer noch nicht vom Tisch ...
Der Code sieht momentan so aus:

Delphi-Quellcode:

procedure TForm1.Prim_re(n,i:integer);
var prim:boolean;

begin
  if n < limit then
  begin
    if i = 1 then List2.Items.Add(IntToStr(n));
    if (n mod i) = 0 then Prim_re(n+1,n)
    else Prim_re(n,i-1);
  end;
end;

Funktioniert auch anscheinend wunderbar, solange man sich auf die Zahlen von 1 bis 293 beschränkt. Alles darüber bringt einen StackOverflow.
Aus irgendeinem Grund sieht der Stack so aus:

TForm1.Prim_re(???,???)
TForm1.Prim_re(293,2147350260)
TForm1.Prim_re(293,266)
TForm1.Prim_re(293,267)
TForm1.Prim_re(293,268)
... usw, usw

Wie kommt es dazu, dass der Speicher auf einmal so spinnt? Kennt sich vllt jemand damit aus?

[FAlter]

Hi,

der Stack ist nicht unendlich groß. Normalerweise ist die Obergrenze 64 KiB, kann aber bis auf 16 MiB angehoben werden (Projektoptionen->Linker->Max. Stackgröße->Größe eintragen).

Mfg
FAlter

[evilhomer]

Okay, danke! Nun sind bereits die Zahlen bis 1000 drin, aber so eine richtige Lösung für das Problem fehlt noch immer.
Wenn ich das gleiche auf dem iterativen Weg mit zwei Schleifen rechnen lasse, sind einige 100000 drin ohne dass sich der Stack meldet, d.h. hier kann es doch nicht so Speicher-intensiv sein?

[Apollonius]

Ja, natürlich. Der große Nachteil von rekursiven Lösungen ist immer der Stack-Verbrauch, der bei iterativen Varianten nicht so horrend ist.

[FAlter]

Hi,

ich glaube, du hast noch nicht wirklich verstanden, wie das mit dem Stack abläuft.

Ganz einfaches Beispiel:

Delphi-Quellcode:

procedure foo;
begin 
  while ... do
    ...;
end;

procedure bar;
begin
  ...
  if ... then
    bar;
end;

Foo soll hier iterativ arbeiten. Es gibt keine Parameter oder lokale Variablen, also landet nur beim Aufruf die Rücksprungadresse (also da, von wo aufgerufen wurde und nach verlassen weitergearbeitet werden soll), auf dem Stack. Während Foo arbeitet, verändert sich die Größe des Stacks nicht (es sei denn, Foo ruft etwas weiteres auf, bei Rückkehr zu Foo wird wieder die alte Größe erreicht).

Bar hingegen arbeitet rekursiv. Während bar arbeitet, ruft es sich selbst auf - entsprechend oft landet die Speicheradresse auf dem Stack, von der bar sich selbst aufruft. Erst beim Verlassen eines bars wird der Wert wieder entfernt. Wenn Bar fertig ist, werden nach und nach alle bars verlassen, und der Stack wird wieder kleiner. Hier werden maximal Rekursionstiefe mal Rücksprungadressen abgelegt. Der Stack wird also viel mehr beansprucht.

Rekursive Funktionen sind immer Stackintensiver als iterative. Das zeigt sich deutlich an diesem Beispiel:

Delphi-Quellcode:

function fakultaet(Zahl: Cardinal): Double;
begin
  if Zahl <= 1 then
    Result := 1
  else
    Result := Zahl * fakultaet(Zahl-1);
end;

function fakultaet(Zahl: Cardinal): Double;
begin
  Result := 1;
  while Zahl > 1 do
  begin
    Result := Zahl * Result;
    Zahl := Zahl - 1;
  end;
end;

Die iterative Funktion ruft keine weiteren Funktionen auf, die Rekursive Funktion hingegen sich selbst - und das Zahl - 2 mal. Sie belegt (Zahl - 2) * 4 Bytes mehr auf dem Stack - alleine schon für die Rücksprungadressen. Hinzu kommt noch der Parameter - auch, wenn Register die Aufrufkonvention ist, denn dasselbe Register wird für den nächsten Aufruf ja mit einem neuen Wert belegt, der alte wird jedoch noch später für die Multiplikation benötigt.

Mfg
FAlter