Mein Stack läuft dauernd über

[Dax]

Hilfe!!!

Ich habe bei mir die Stackgröße auf Max gesetzt(16777216) und er läuft trotzdem dauernd über. Kann mir jemand helfen?? Wie kriege ich einen "ewig" großen Stack??????

[sakura]

16MB sollten eigentlich für alles normalsterbliche reichen. Was machst Du denn, dass Du noch mehr brauchst. Eigentlich hört sich das nach einer fehlgeleiteten Rekursion an.

......

[Dax]

Na ja, gut es ist eine Rekursion, die Ackermannfunktion. Aber fehlgeleitet sollte sie nicht sein...

[Luckie]

Zitat:

Mein Stack läuft dauernd über.

Stell einen Eimer drunter, sonst gibt es feuchte Füße.

Zitat von gecko2000:

Na ja, gut es ist eine Rekursion, die Ackermannfunktion. Aber fehlgeleitet sollte sie nicht sein...

Zeig mal Code. Da stimmt was nicht, auch wenn du überzeugt bist, dass alles stimmt.

[Phoenix]

Hi,

anscheinend hat er recht, denn das gleiche Problem tritt auch bei mir auf:

Delphi-Quellcode:

function TForm1.ack(x,y : integer) : Integer;
begin
{ Die Ackermann - Definition:

                    [ y + 1              wenn x = 0;
      A(  x,  y) =  [ A( x-1 ,1)         wenn y = 0;
                    [ A( x-1, A(x, y-1)  in jedem anderen Fall;

}
    if (x <> 0) and (y <> 0) then
      result := ack(x-1, ack(x,y-1))
    else
      if (y = 0) then
         result := ack(x-1, 1)
      else
         result := y+1;
end;

Die Definition kommt von http://www.loisch.de/, findet sich so aber auch an mehreren anderen Stellen.

Wird nun Ack(0,0) aufgerufen, sprich: rutscht in Folge davon dann x ins Negative, haben wir eine unendlich Rekursion. Oder widerlegt mir das ein Mathematiker?

Auf jeden Fall führt eine unendliche Rekursion zu einem Stack-Overflow, und der lässt sich hier nicht wirklich vermeiden, oder?

Edit: Text etwas umformuliert um's verständlich zu machen

[sakura]

Hier erst einmal die Definition der Ackermannschen Funktion.

Code:

m = 0         ==>   A(0, n) = n+1  
m > 0, n = 0  ==>   A(m, 0) = A(m-1, 1)  
m > 0, n > 0  ==>   A(m, n) = A(m-1, A(m, n-1))

Dass heisst, dass die Ausgangswerte m und n immer größer oder gleich Null (m=>0; n=>0) sein müssen. Aufgrund dieser Festlegung können diese auch nicht kleiner Null werden.

Wenn m null erreicht liefert die Funktion den Nachfolger von n zurück.
Ansonsten:
Wenn n null erreicht liefert die Funktion den Nachfolger von A(m-1, 1) zurück.
Ansonsten:
Ist das Ergebnis A(m-1, A(m, n-1))

Darin lag auch der Fehler in der Lösung von Phoenix. Du überprüfst zuerst, ob n (y) Null erreicht hat!, aber Du musst zuerst m (x) überprüfen. Dann können die Zahlen auch nie negativ werden.

Es stimmt allerdings, dass diese Funktion schnell die Grenzen des Stacks erreichen kann - (mehr oder weniger) deshalb wurde diese auch entwickelt.

......

P.S. Hier noch ein Link: http://www.kosara.net/thoughts/ackermann.html

[Dax]

Ich zeig euch mal den Code(bei dem der Stack auch überläuft, aber erst nach laaaaaaanger Zeit):

Delphi-Quellcode:

unit AckerCalc;

interface

uses
  Windows, Messages, SysUtils, Classes;

type
  TAckerCalcEvent = procedure(X, Y, Result, NumberOfResult: integer; Calls: int64) of object;
  TAckerMethod = procedure of object;
  TAckerCalc = class;
  TCalcThread = class(tthread)
  private
    Owner: TAckerCalc;
    x, y, x1, y1: integer;
    function run(x, y: integer): integer;
  protected
    procedure execute; override;
  end;
  TAckerCalc = class(tcomponent)
  private
    FCalc: TCalcThread;
    FPriority: TThreadPriority;
    FDone, FCancel, FPause, FResume, FStart: TAckerMethod;
    FDoneOne: TAckerCalcEvent;
    FX, FY, FX1, FY1: integer;
    procedure Done; dynamic;
    procedure DoneOne; dynamic;
    function FCaretX: integer;
    function FCaretY: integer;
    function FCaretCalls: int64;
  protected
  public
    constructor Create(AOwner: TComponent); override;
    destructor Destroy; override;
  published
    procedure Start;
    procedure Pause;
    procedure Resume;
    procedure Cancel;
    procedure ChangePriority(Priority: TTHreadPriority);
    property CaretX: integer read FCaretX;
    property CaretY: integer read FCaretY;
    property CaretCalls: int64 read FCaretCalls;
    property ThreadPriority: TThreadPriority read FPriority write FPriority;
    property OnDone: TAckerMethod read FDone write FDone;
    property OnDoneOne: TAckerCalcEvent read FDoneOne write FDoneOne;
    property OnCancel: TAckerMethod read FCancel write FCancel;
    property OnPause: TAckerMethod read FPause write FPause;
    property OnResume: TAckerMethod read FResume write FResume;
    property OnStart: TAckerMethod read FStart write FStart;
    property BeginAtX: integer read FX write FX;
    property BeginAtY: integer read FY write FY;
    property EndAtX: integer read FX1 write FX1;
    property EndAtY: integer read FY1 write FY1;
  end;

procedure Register;

implementation

var
  c: int64;
  cx, cy, result, d: integer;

procedure Register;
begin
  RegisterComponents('Gecko', [TAckerCalc]);
end;

constructor TAckerCalc.Create(AOwner: TComponent);
begin
  inherited create(AOwner);
end;

destructor TAckerCalc.Destroy;
begin
  inherited destroy;
end;

procedure TAckerCalc.Done;
begin
  if not FCalc.Terminated then
  begin
    if assigned(OnDone) then FDone;
  end;
end;

procedure TACkerCalc.Start;
begin
  d := 0;
  FCalc := TCalcThread.Create(true);
  FCalc.Priority := FPriority;
  FCalc.Owner := self;
  FCalc.x := FX;
  FCalc.y := FY;
  FCalc.x1 := FX1;
  FCalc.y1 := FY1;
  if assigned(OnStart) then FStart;
  FCalc.Resume;
end;

procedure TAckerCalc.DoneOne;
begin
  inc(d);
  if assigned(OnDoneOne) then FDoneOne(cx, cy, result, d, c)
end;

procedure TAckerCalc.Cancel;
begin
  FCalc.Terminate;
  if assigned(OnCancel) then FCancel;
end;

procedure TAckerCalc.Pause;
begin
  FCalc.Suspend;
  if assigned(OnPause) then FPause;
end;

procedure TAckerCalc.Resume;
begin
  FCalc.Resume;
  if assigned(OnResume) then FResume;
end;

function TAckerCalc.FCaretX: integer;
begin
  result := cx;
end;

function TAckerCalc.FCaretY: integer;
begin
  result := cy;
end;


function TAckerCalc.FCaretCalls: int64;
begin
  result := c;
end;

procedure TAckerCalc.ChangePriority(Priority: TTHreadPriority);
begin
  FCalc.Suspend;
  FCalc.Priority := Priority;
  FCalc.Resume;
end;

{*****************************************************************************}

procedure TCalcThread.execute;
var a, b: integer;
begin
  for a := x to x1 do
  for b := y to y1 do
  begin
    c := 0;
    if terminated then break;
    result := run(a, b);
    cx := a;
    cy := b;
    if not terminated then synchronize(Owner.DoneOne);
  end;

  if not terminated then
  synchronize(Owner.Done);
  terminate;
end;

function TCalcThread.run(x, y: integer): integer;
begin
  while suspended do{nix};
  inc(c);
  cx := x;
  cy := y;
  if terminated then exit;
  if x = 0 then result := y + 1 else
  if (x <> 0) and (y = 0) then result := run(x - 1, 1) else
      result := run(x - 1, run(x, y-1));
end;

end.

Übrigens: das hier ist meine Kompo dazu

[Luckie]

Zitat von gecko2000:

Ich zeig euch mal den Code(bei dem der Stack auch überläuft, aber erst nach laaaaaaanger Zeit):

Gut.

Zitat:

Übrigens: das hier ist meine Kompo dazu

Nicht so gut.

Bitte poste beim nächsten mal nur den relevanten Code oder häng es an.

[Dax]

Mir geht es ja zm die Berechnung, also ist eigentlich dir .run-Prozedur der relevante Code, aber mönnte die .execute-Methode auch noch dazunehmen.

MfG gecko2000

[Dax]

Die eigentliche Funktion sieht so aus:

Delphi-Quellcode:

procedure run;
begin 
  if x = 0 then result := y + 1 else 
  if (x <> 0) and (y = 0) then result := run(x - 1, 1) else 
      result := run(x - 1, run(x, y-1)); 
end;