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.

...:cat:...

[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. :mrgreen:

Zitat:

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.

...:cat:...

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:

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;