Prolog - Rekursion

[Philipp]

Hi,

kann mir einer die Rekursion erkläre, bitte. Ich verstehe das nicht:

letztes_element(X,[X]).
letztes_element(X,[Y|YS]) :- letztes_element(X,YS).

Hier ist ein Beispiel in Prolog, könnt ihr mir erklären wie Prolog vorgeht und warum es eine Schleife gibt.

Danke

[leo]

Hallo,

Hi,

kann mir einer die Rekursion erkläre, bitte. Ich verstehe das nicht:

letztes_element(X,[X]).
letztes_element(X,[Y|YS]) :- letztes_element(X,YS).
Hier ist ein Beispiel in Prolog, könnt ihr mir erklären wie Prolog vorgeht und warum es eine Schleife gibt.

Wenn ich mich recht erinnere:
Das letzte Element einer Liste die nur ein Element enthält ist dieses Element (letztes_element(X,[X]).)
Ansonsten wird die Liste in Kopf (Y, erstes Element) und den Rest (YS) gespalten und mit der Restliste YS erneut die Funktion letztes_element aufgerufen (Rekursion, Funktion ruft sich selbst auf). Das ganze dann eben solange wie YS mehr als ein Element enthält, denn dann gilt die erste Definition von letztes_element als Abbruchbedingung.

Danke

Bitte, hoffentlich war es einigermaßen verständlich :-)

MfG, leo

[Philipp]

Vielen Dank für deine Antwort, jedoch versteh ich immer noch nicht wie diese Schleife zustande kommt.

[Heiner]

Aaaalso,

Prolog arbeitet das Prädikat von oben nach unten ab. Dieses Prädikat besteht aus zwei Zeilen. Es wird also geschaut, ob X Teil der Liste [X] ist, also etwa. letztes_element(beispiel,[beispiel]). Dann stoppt Prolog und liefert true.

Wenn aber etwa anderes in der Liste steht, wird die erste Zeile nicht ausgeführt, da sie nicht anwendbar ist, denn letztes_element(beispiel,[wasanderes]) erfüllt nicht die erste Zeile.

In der zweiten Zeile passt hingegen vieles. Etwa passt
letztes_element(beispiel,[kopf|rest]). Daher wird letzes_element mit den Werten aufgerufen. X=beispiel und YS=rest, daher beginnt eine Rekursion. :- signalisiert, dass das gleiche Prädikat wieder aufgerufen wird, eben mit beispiel, rest.

letztes_element(X,[X]).
letztes_element(X,[Y|YS]) :- letztes_element(X,YS).

Wenn Du nun eine Abfrage startest, also beispielweise
letztes_element(X, [Hans, Peter, Ulrike]). abfragst, dann kann das erste Prädikat nicht wirken, da X ungleich Hans, Peter, Ulrike, da X keine Liste ist und daher nur ein Element enthält. Es würde nur X=Ulrike liefern, wenn Du zum Beispiel letztes_element(X, [Ulrike]). abfragen würdest.

Bei der längeren Liste hingegen wird die zweite Zeile wirksam, die sich dann mit letztes_element(X, [Peter, Ulrike]) und in der zweiten Rekursion mit l_e(X, [Ulrike]) aufruft. Hier ist endlich etwas erreicht, was die Abbruchbedingung, also die erste Zeile annehmen kann.

Kapiert?
Heiner