Rekursion abrechen

Stauch · Beiträge: 140 Win 2000, Win XP D4

Ich nutze eine Rekursive Prozedur um einen Eintrag zu finden. Wie kann ich die suche komplett abbrechen, wenn der gesuchte Eintrag gefunden wurde?

wwerner · Beiträge: 185

Lies dir deine Frage noch mal durch. Sie ist so allgemein gehalten, das es darauf nur die Antwort geben kann: In dem du ein Endeflag hast

_________________
Gruß

Wolfgang

----------
zu hause ist es doch am schönsten

Stauch · Beiträge: 140 Win 2000, Win XP D4

Was ist ein EndFlag?

wwerner · Beiträge: 185

Irgend eine Variable oder eine Bedingung, die sagt, das die Rek. beendet werden soll

_________________
Gruß

Wolfgang

----------
zu hause ist es doch am schönsten

Stauch · Beiträge: 140 Win 2000, Win XP D4

Alles Klar. Ich hatte gehofft, sowas ähnliches wie exit verwenden zu können, um damit alle Aufrufbäume zu beenden.

Mein Pseudocode sieht so aus

markieren

Quelltext

1:
2:
3:
4:
5:

 if (not gefunden) then
                                   if (wort=suchwort) then gefunden:=true
                                   else
                                   if (not gefunden) and (...) then rek. aufruf1
                                   if (not gefunden) and (...) then rek. aufruf2

Ich möchte die sache halt etwas beschleunigen
MfG C.

Gast Erhaltene Danke: 1

Z.B. so:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:

var
  Form1: TForm1;
  i: Word = 0;

implementation

{$R *.DFM}

procedure Test;
begin
  if i > 10 then Exit;

  Inc(i);
  Test;
end;

procedure TForm1.Button1Click(Sender: TObject);
begin
  Test;
  ShowMessage(IntToStr( i ));
end;

Für jeden rekursiven Aufruf muß auch ein mal ein Exit stehen. Wenn also die Prozedur 10 mal aufgerufen wird, dann wird auch weitere 10 mal if i > 10 then aufgerufen (zusammen also 20mal).

Klabautermann · Verfasst: Mo 04.11.02 18:09

Hallo,

ich finde es übersichtlicher, wenn man die Abbruchbedingung direckt mit dem Rekursiven Aufruf verbindet.
Popov's procedure sähe dann so aus:

markieren

Quelltext

1:
2:
3:
4:

if (i < 10) then begin
 Inc(i);
 Test(i);
end;

Gruß
Klabautermann

Stauch · Beiträge: 140 Win 2000, Win XP D4

Öhm, ja ... bilde mir ein eure Beispiele zu verstehen, aber sehe nicht so richtig, wie mir das weiter hilft. Vielleicht doch mal der Code:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

procedure check(wort:string;nr:integer);
 begin
  if (not gefunden) then
    begin
    if (wort=pwd) then begin
                       gefunden:=true;
                       showMessage(wort);
                       exit;
                       end
                  else begin
     if (length(wort)< max) and (not gefunden) then check(wort+Mzeichen[0],0);                        
                        end;

     if (nr<maxnr) and (not gefunden) then begin
                        wort[length(wort)]:=Mzeichen[nr+1];
                        check(wort,nr+1);
                        end;
    end;
 end;

Dabei ist MZeichen ein Array of char (der Zeichenvorrat) und gefunden eine boolsche Variable.
Ich würde gern die Anzahl der Bedingungen verringern, um die Suchgeschwindigkeit zu erhöhen, aber die Rekursion soll auch sofort abbrechen, wenn das Suchwort gefunden wurde.
MfG C.

Udontknow · Beiträge: 2596 Win7 D2006 WIN32, .NET (C#)

Bringe einen weiteren Parameter Tiefe ins Spiel. Den übergibst du bei jedem Aufruf der Prozedur Check um 1 erhöht. Sobald er bspw. >10 ist, kannst du gefunden auf true setzen und exit aufrufen.

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:

procedure check(wort:string;nr:integer;Tiefe:Integer=0); 
begin 
  if Tiefe=10 then 
  begin
    gefunden:=True;
    exit;
  end;

  if (not gefunden) then 
    begin 
    if (wort=pwd) then begin 
                       gefunden:=true; 
                       showMessage(wort); 
                       exit; 
                       end 
                  else begin 
     if (length(wort)< max) and (not gefunden) then check(wort+Mzeichen[0],0,Tiefe+1);                        
                        end; 

     if (nr<maxnr) and (not gefunden) then begin 
                        wort[length(wort)]:=Mzeichen[nr+1]; 
                        check(wort,nr+1,Tiefe+1); 
                        end; 
    end; 
end;

Cu,
Udontknow

Stauch · Beiträge: 140 Win 2000, Win XP D4

So scheints zu gehen. Vielen Dank an alle :D

C.

_________________
Geht das? Und wenn ja, warum nicht?

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme