Probleme mit Rekursion

Computer: Software & Programmierung Delphi & Pascal
#1

Hallo,

ich habe irgendwie ein Problem zu erkennen, das in dem folgenden Programm genau an den Ausgangspunkt zurückgekehrt wird.

Das ganze läuft unter „Niki, der Roboter“, eine für Schüler geschaffene Umgebung in der Turbo Pascal unterrichtet werden soll.

Die benutzten Befehle sind alle entweder in der Umgebung schon definiert oder vor dem Program definiert, also da ist nicht das Problem.

Der Roboter soll von einer Startposition bis zu einem Hindernis laufen , sich dann umdrehen und zum Ausgangspunkt zurückehren.

procedure Hin_Rueck;
begin
Pruef_frei;
if (not frei)
then
begin
Umdrehen;
end
else
begin
vor;
Hin_Rueck;
vor;
end;
end;

begin
Init;
Hin_rueck;
readln; { warten}
end.

Wäre toll, wenn mir da jemand auf die Sprünge helfen kann, sollte eigentlich erklärbar sein, aber ich seh´s nicht.

Einen schönen Abend.

Gruß Volker

#2

Hallo Volker,

ich habe irgendwie ein Problem zu erkennen, das in dem
folgenden Programm genau an den Ausgangspunkt zurückgekehrt
wird.

So wird es klarer:

uses crt;

var
 x, y: Byte;
 frei: Boolean;
 vorwaerts: Boolean;

procedure pruef\_frei;
begin
 frei := (x ');
 inc(X);
 end
 else begin
 write('

In Worten: 
 - Schau ob frei ist
 - ja, also gehe einen Schritt vor
 - Schau ob frei ist
 ...
 - Schau ob frei ist
 - nein, drehe dich um (Richtung wechselt, nun treten alle vor-Befehle in Kraft, die aufgrund der Rekursion noch nicht ausgeführt wurden}
 - Gehe zurück
 - Gehe zurück
 .... (genauso oft, wie vorgegangen wurde)

Schönen Gruß,
Rudy
#3

Hallo,

ich habe irgendwie ein Problem zu erkennen, das in dem
folgenden Programm genau an den Ausgangspunkt zurückgekehrt
wird.

nicht nur Du… *grins*

Der Roboter soll von einer Startposition bis zu einem
Hindernis laufen , sich dann umdrehen und zum Ausgangspunkt
zurückehren.

OK.

procedure Hin_Rueck;
begin
Pruef_frei;
if (not frei)
then
begin
Umdrehen;
end
else
begin
vor;
Hin_Rueck;
vor;
end;
end;

begin
Init;
Hin_rueck;
readln; { warten}
end.

Was bewirkt „vor“ genau? Die Antwort auf diese Frage ist wichtig.

Wäre toll, wenn mir da jemand auf die Sprünge helfen kann,
sollte eigentlich erklärbar sein, aber ich seh´s nicht.

Ich versteh nicht mal, was mit der Rekursion bei diesem Problem überhaupt bezweckt werden soll.

Mit freundlichem Gruß
Martin

#4

Hallo Martin,

zunächst vielen Dank für die schnelle Antwort.

Was bewirkt „vor“ genau? Die Antwort auf diese Frage
ist wichtig.

Der Roboter soll einen Schritt vorwärst gehen.

Ich versteh nicht mal, was mit der Rekursion bei diesem
Problem überhaupt bezweckt werden soll.

Die „Niki-Umgebung“ kennt keine (sichtbare, verwendbaren) Variablen, deshalb wird als Lösung diese rekursive Variante angeboten.

Gruß Volker

#5

Hallo Rudy,

auch an Dich, „Herzlichen Dank für die schnelle Antwort“.

Sorry, ich hätte vielleicht doch das ganze Programm posten sollen, Du hast es bis auf andere namen, Typen genauso gemacht, wie ich es habe.

Soweit alles klar.

  • nein, drehe dich um (Richtung wechselt, nun treten alle
    vor-Befehle in Kraft, die aufgrund der Rekursion noch nicht
    ausgeführt wurden}

Vermtl. liegt hier mein Problem, läuft hier also im Hintergrund ein Zähler mit, der sich merkt, wie oft die Prozedur aufgerufen wurde?

Das würde die richtige Anzahl der „Rückschritte“ erklären.

Aber auch dann, warum springt der Aufruf nicht an den Anfang der Procedure zurück?

  • Gehe zurück
  • Gehe zurück
    … (genauso oft, wie vorgegangen wurde)

Jo, das ist genau mein Problem.

Schönen Abend noch.

Gruß Volker

#6

Hallo Volker,

Vermtl. liegt hier mein Problem, läuft hier also im
Hintergrund ein Zähler mit, der sich merkt, wie oft die
Prozedur aufgerufen wurde?

Der ‚Zähler‘ ist der Stack. Wenn eine Rekursion betreten wird, also eine Funktion/Prozedur sich selbst aufruft, dann läuft die Funktion an dieser Stelle nicht weiter, sondern füllt an dieser Stelle den Stack (Speicher) und merkt sich den Eintrittspunkt in die Rekursion. Dann läuft sozusagen eine neue Funktion an dieser Stelle weiter (ungeachtet, dass es die Funktion selbst ist). Das geht so lange weiter, bis die Abbruchbedingung erfüllt ist (=umdrehen, dort wird keine Rekursion aufgerufen, gewissermaßen ist die Prozedur also beendet) oder der Stack voll ist (overflow-Error, passiert bei fehlerhaften Rekursionen, die nicht abbrechen oder zu speicherlastig sind). Sobald der rekursive Aufruf beendet ist, läuft die ‚alte‘ Funktion wieder weiter und so fort.

Das würde die richtige Anzahl der „Rückschritte“ erklären.
Aber auch dann, warum springt der Aufruf nicht an den Anfang
der Procedure zurück?

Der Stack wird nach Erfüllung der Abbruchbedingung einfach wieder nach unten abgearbeitet, also alle Funktionen beenden den Durchlauf ab der Stelle, wo sie sich selbst vorher aufgerufen haben. Dadurch, dass sich die Richtung geändert hat, verursacht dies Rückschritte, und klarerweise sind es genauso viele wie Schritte vorwärts.

An Deinem Beispiel:

1) ------------------------ Wird so lange wiederholt, bis Abbruchbedingung erfüllt ist
procedure hin\_rueck; \>\>\>\>\>^ -----
Ich hoffe ich habe es einigermaßen einfach veranschaulichen können :smile:

Ciao,
Rudy
#7

Hallo Rudy,

Der ‚Zähler‘ ist der Stack. Wenn eine Rekursion betreten wird,
also eine Funktion/Prozedur sich selbst aufruft, dann läuft
die Funktion an dieser Stelle nicht weiter, sondern füllt an
dieser Stelle den Stack (Speicher) und merkt sich den
Eintrittspunkt in die Rekursion. Dann läuft sozusagen eine
neue Funktion an dieser Stelle weiter (ungeachtet, dass es die
Funktion selbst ist). Das geht so lange weiter, bis die
Abbruchbedingung erfüllt ist (=umdrehen, dort wird keine
Rekursion aufgerufen, gewissermaßen ist die Prozedur also
beendet) oder der Stack voll ist (overflow-Error, passiert bei
fehlerhaften Rekursionen, die nicht abbrechen oder zu
speicherlastig sind). Sobald der rekursive Aufruf beendet ist,
läuft die ‚alte‘ Funktion wieder weiter und so fort.

Das würde die richtige Anzahl der „Rückschritte“ erklären.
Aber auch dann, warum springt der Aufruf nicht an den Anfang
der Procedure zurück?

Der Stack wird nach Erfüllung der Abbruchbedingung einfach
wieder nach unten abgearbeitet, also alle Funktionen beenden
den Durchlauf ab der Stelle, wo sie sich selbst vorher
aufgerufen haben. Dadurch, dass sich die Richtung geändert
hat, verursacht dies Rückschritte, und klarerweise sind es
genauso viele wie Schritte vorwärts.

So langsam wird´s verständlich, allerdings kannte ich eine „Stack-Orientierung“ nur von Forth, wenn man von Assembler absieht.

Aber jetzt mache ich erstmal Schluß, vielen Dank, ich grüble morgen weiter.

Gruß Volker

#8

Hallo Volker,

Was bewirkt „vor“ genau? Die Antwort auf diese Frage
ist wichtig.

Der Roboter soll einen Schritt vorwärst gehen.

OK.

Die „Niki-Umgebung“ kennt keine (sichtbare, verwendbaren)
Variablen, deshalb wird als Lösung diese rekursive Variante
angeboten.

Alles klar, mit diesem Hintergrund gibt die Sache Sinn.

Guck Dir das folgende Schema an – dann verstehst Du sicher sofort, was passiert (die Zeilen, die abgearbeitet werden, sind fett markiert):

**prueffrei;**

IF NOT frei THEN [vor;
 --------------------
 | **prueffrei;**
 |
 | IF NOT frei THEN [vor;
 | -------------------
 | | **prueffrei;**
 | |
 | | IF NOT frei THEN [vor;
 | | -------------------
 | | | **prueffrei;**
 | | |
 | | | IF NOT frei THEN [vor;
 | | | -------------------
 | | | | **prueffrei;**
 | | | |
 | | | | IF NOT frei THEN [vor;
 | | | | -------------------
 | | | | | **prueffrei;**
 | | | | |
 | | | | | IF NOT frei THEN [umdrehen
 | | | | | end
 | | | | | ELSE
 | | | | | begin
 | | | | | ...
 | | | | | end
 | | | | -------------------
 | | | | **vor**
 | | | | end
 | | | -------------------
 | | | **vor**
 | | | end
 | | -------------------
 | | **vor**
 | | end
 | -------------------
 | **vor**
 | end
 --------------------
**vor**
 end

Schreibst Du alle Zeilen, die abgearbeitet werden, nochmal untereinander…

**pruef\_frei** (Prüfung ergibt "frei")
**vor**
**pruef\_frei** (Prüfung ergibt "frei")
**vor**
**pruef\_frei** (Prüfung ergibt "frei")
**vor**
**pruef\_frei** (Prüfung ergibt "frei")
**vor**
**pruef\_frei** (Prüfung ergibt "frei")
**vor**
**pruef\_frei** (Prüfung ergibt "NICHT frei")
**umdrehen**
**vor**
**vor**
**vor**
**vor**
**vor**

…siehst Du, dass sich der Roboter genau fünf mal in Richtung seiner Nase bewegt, sich dann umdreht, und sich anschließend abermals genau fünf Schritte in Richtung seiner Nase bewegt (wobei er jetzt relativ zum Tisch _zurück_geht).

Ist es jetzt klarer geworden?

Mit freundlichem Gruß
Martin

#9

Danke
an euch Beiden,

die Erklärungen haben mir sehr geholfen.

Ich verstehe, schweife jetzt etwas ab, dass dies rekursive Programmieren einfacher sein soll als eine Variable.
Mir fehlen in der Umgebung einfach die Variablen, mal schauen, ich werde wohl auf eine „normale“ Pascal-Umgebung umsteigen.

Gruß Volker