Stack Overflow

[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