Un/gerade - Indirekte Rekursion

[n00b_on_knees]

Hallo Miteinander!

Ich hoffe hier gibt es ein paar die sich mit der Indirekten Rekursion auskennen!
Das folgende Beispiel soll ausgeben, ob die eingegebene Zahl oder die um 1 verminderte gerade oder ungerade ist, weiters soll ausgegeben werden, in welcher Funktion das ganze geprüft wurde. Ich glaube ich Blicke hier im Moment nichtmehr durch, obwohl es wohl eventuell simpel sein wird. Wenn ich zum Beispiel irgendeine Ungerade Zahl wie 43 eingebe, wird die Zahl um 1 vermindert, und in der Funktion Odd ausgegeben, das die Zahl 42 ungerade ist.
Das Lösungsverfahren mit pred ist vorgegeben, wenn ich es weglasse kommt es sowieso zu einem Stack überlauf, sowie wenn ich die If Abfragen Bedinungen ändere.

Ich werde hier den Quellcode posten, sowie die Datei anfügen, vielleicht findet sich der Fehler ja schon beim Quelltext-sehen.

Ich hoffe ihr könnt mir helfen,
mit freundlichen Grüßen
n00b_on_knees

Delphi-Quellcode:

function TForm1.odd(x: integer): boolean;
begin
  if (x mod 2 = 0) then
    begin
      result:= false;
      mmAus.Lines.Add('Die Zahl ' + IntToStr(x) + ' ist Ungerade');
      mmAus.Lines.Add('Die Ausgabe befindet sich in der Funktion Odd');
    end
  else
    result:= even(pred(x));
end;

function TForm1.even(x: integer): boolean;
begin
  if (x mod 2 = 0) then
    begin
      result:= true;
      mmAus.Lines.Add('Die Zahl ' + IntToStr(x) + ' ist Gerade');
      mmAus.Lines.Add('Die Ausgabe befindet sich in der Funktion Even');
    end
  else
    result:= odd(pred(x));
end;

procedure TForm1.btStartClick(Sender: TObject);
var
  x: integer;
begin
  x:= StrToInt(edZahl.Text);
  even(x);
end;
end.

[Sharky]

Hai n00b_on_knees,



Du prüfst in beiden deiner Funktionen ob x gerade ist!

[edit=Admin]Irgendwas war da schief gelaufen :-/ Mfg, Daniel[/edit]

[axelf98]

Beim ersten Durchblick ist mir aufgefallen, dass beide Funktionen die gleiche Abfrage haben...
Dann springt er bei Nichterfüllung einer Abfrage zur nächsten, bis ein Stack-Überlauf kommt!

Delphi-Quellcode:

function TForm1.odd(x: integer): boolean;
begin
  if (x mod 2 = 0) then
   ....
end;

function TForm1.even(x: integer): boolean;
begin
  if (x mod 2 = 0) then
    begin
   ....
end;

[axelf98]

Hmm, irgendwie stimmt da was mit der Anzeige nicht! Da hat sich was verschoben bei mir!
(IE und Opera , siehe Anhang)

[Daniel B]

Habs auch gesehen, aber nach Deinem Post jetzt ist es weg.

[n00b_on_knees]

Zitat:

Zitat von axelf98

Beim ersten Durchblick ist mir aufgefallen, dass beide Funktionen die gleiche Abfrage haben...
Dann springt er bei Nichterfüllung einer Abfrage zur nächsten, bis ein Stack-Überlauf kommt!

Delphi-Quellcode:

function TForm1.odd(x: integer): boolean;
begin
  if (x mod 2 = 0) then
   ....
end;

function TForm1.even(x: integer): boolean;
begin
  if (x mod 2 = 0) then
    begin
   ....
end;

hierbei ist bei mir kein stack überlauf, lediglich wenn ich eben die if-abfrage ändere (zb in x mod 2 <>0),....ohne ändern kommt das mit zb 42 statt 43 ungerade heraus.

[himitsu]

Hi axelf98,
du meinst das, da beide Funktionen die gleiche Abfrage haben, es zum Stack-Überlauf kommen kann.
Dem ist nicht so.
Also wenn einer dieser Funktionen eine gerade Zahl übergeben wird, kommt der Text und die Funktion wird beendet.
Wenn aber einer dieser Funktionen eine ungerade Zahl übergeben wird, wird deren Vorgänger (X - 1) an die Andere weitergegeben. Da es dann ja eine gerade Zahl ist, kommt dort der Text und die beiden Funktion werden ebenfalls beendet.

@n00b_on_knees,
ich verstehe nur nicht wo dein Problem ist, es scheint doch zu funktionieren?

:nerd: Bloß eine Ausgabe wie z.B. "Die Zahl 42 ist Ungerade" klingt ein bissel blöd, da ja nicht 42 sondern ihr Nachfolger (43) ungerade ist.


Abfrage ob gerade - bei ja - Ausgabe das die "gerade" Zahl ungerade ist.

Delphi-Quellcode:

function TForm1.odd(x: integer): boolean;
begin
  if (x mod 2 = 0) then begin
    result:= false;
    mmAus.Lines.Add('Die Zahl ' + IntToStr(x) + ' ist Ungerade');

Es sollte zum Beispiel so aussehen:

Delphi-Quellcode:

function TForm1.odd(x: integer): boolean;
begin
  if (x mod 2 = 0) then begin
    result:= false;                                  {v}
    mmAus.Lines.Add('Die Zahl ' + IntToStr(x) + ' ist Gerade');

{oder}

function TForm1.odd(x: integer): boolean;
begin
  if (x mod 2 = 0) then begin
    result:= false;                       {v}
    mmAus.Lines.Add('Die Zahl ' + IntToStr(Succ(x)) + ' ist Ungerade');

{oder}

function TForm1.odd(x: integer): boolean;
begin
  if (x mod 2 = 0) then begin
    result:= false;     {v}
    mmAus.Lines.Add('Der Nachfolger der Zahl ' + IntToStr(x) + ' ist Ungerade');

[axelf98]

Der Stacküberlauf hängt mit dem pred(x) zusammen:
Immer, wenn die Zahl nicht gerade ist, wird geprüft ob sie ungerade ist. Aber sie wird zuvor durch pred(x) wieder gerade gemacht, und deshalb hat man immer genau die falsche Zahl in der Abfrage und die Gehschichte geht ins unendliche...

So wies unten ist, funktionierts:

Delphi-Quellcode:

unit fUnGerade;

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;

type
  TForm1 = class(TForm)
    btStart: TButton;
    mmAus: TMemo;
    edZahl: TEdit;
    procedure btStartClick(Sender: TObject);
    function odd(x: integer): boolean;
    function even(x: integer): boolean;
  private
    { Private-Deklarationen }
  public
    { Public-Deklarationen }
  end;

var
  Form1: TForm1;

implementation

{$R *.dfm}

function TForm1.odd(x: integer): boolean;
begin
  if (x mod 2 <> 0) then
    begin
      result:= false;
      mmAus.Lines.Add('Die Zahl ' + IntToStr(x) + ' ist Ungerade');
      mmAus.Lines.Add('Die Ausgabe befindet sich in der Funktion Odd');
    end
  else
    result:= even((x));

end;

function TForm1.even(x: integer): boolean;
begin
  if (x mod 2 = 0) then
    begin
      result:= true;
      mmAus.Lines.Add('Die Zahl ' + IntToStr(x) + ' ist Gerade');
      mmAus.Lines.Add('Die Ausgabe befindet sich in der Funktion Even');
    end
  else
    result:= odd((x));
end;


procedure TForm1.btStartClick(Sender: TObject);
var
  x: integer;
begin
  x:= StrToInt(edZahl.Text);
  even(pred(x));
end;
end.

[n00b_on_knees]

Irgendwie ist das wohl so simpel, das ich nicht darauf gekommen bin. Habe das jetzt einfach mal mit der anderen Ausgabe ausprobiert, und es funktioniert. Ich dachte das wenn ich diese Ausgabe ändere, das ganze genau umgekehrt passiert, also bei der Zahl 44 zb. die Zahl 43 ist gerade.

Danke an himitsu, und natürlich alle anderen die gepostet haben!

Edit: Danke die Version funktioniert auch!
Edit2: Nur wohl irgendwie wird mit dieser Version, immer nur Gerade ausgegeben, also nie eine Ungerade Zahl, aber da ich die andere Lösung nehme, ist das jetzt egal ;).

[tommie-lie]

Zitat:

Zitat von axelf98

Der Stacküberlauf hängt mit dem pred(x) zusammen:
Immer, wenn die Zahl nicht gerade ist, wird geprüft ob sie ungerade ist. Aber sie wird zuvor durch pred(x) wieder gerade gemacht, und deshalb hat man immer genau die falsche Zahl in der Abfrage und die Gehschichte geht ins unendliche...

Irgendwie scheinst du da was überlesen zu haben...
Die Zahl 43 wird an even übergeben. 43 mod 2 ist nicht 0, also wird der Vorgänger von 43 (42) an odd übergeben. Dort wird abgefragt, ob 42 mod 2 gleich 0 ist, und das ist der Fall, die Rekursion hört auf. Der Stacküberlauf tritt nur dann ein, wenn in einer Funktion "x mod 2 = 0" und in der anderen "x mod 2 <> 0" abgefragt wird, oder wenn in beiden "x mod 2 = 0" abgefragt wird, aber nicht pred benutzt wird.
So, wie n00b_on_knees' Funktionen vorher waren, hatte das mit dem pred absolut seine Richtigkeit, nur die Ausgabe war nicht ganz korrekt...
Das, was du an Code gepostet hast, ist von der Funktionsweise her identisch mit n00b_on_knees' Code, du hast nur pred ganz rausgelassen und in beiden Funktionen verschiedene Abfragen.


Übrigens ist sowas das scheinbar schlechteste Beispiel für indirekte Rekursionen. Die Rekursion ist (bei richtiger Implementierung :mrgreen:) nach maximal zwei Funktionsaufrufen (jeweils ein Aufruf von zwei Funktionen) erledigt, keine der Funktionen wird zweimal aufgerufen, geschweige denn mehrmals.


Und noch einfacher geht's mit der Funktion odd aus der Unit system.pas :mrgreen: