Rekursive Regeln

Vorfahren

Wir betrachten den Teil-Stammbaum der Halbgötter:

% Fakten
maennlich(zeus).
maennlich(ares).
maennlich(frank).

weiblich(hera).
weiblich(clarissa).

kind(ares,zeus).
kind(ares,hera).
kind(clarissa,ares).
kind(frank,ares).

% Regeln

elternteil(VORFAHR, NACHFAHR) :- kind(NACHFAHR, VORFAHR).

Aufgabe 1

Ergänze die folgenden Regeln.

% Regeln

elternteil(VORFAHR, NACHFAHR) :- kind(NACHFAHR, VORFAHR).
grosselternteil(VORFAHR,NACHFAHR) :- elternteil(PERSON,NACHFAHR), ...
urgrosselternteil(VORFAHR,NACHFAHR) :- elternteil(PERSON,NACHFAHR), grosselternteil( ...
ururgrosselternteil( ...

Rekursive Regeln

Das Bildungsschema der Regeln ist immer gleich und klar zu erkennen.
In Worten:

• Ein [VORFAHR ist Elternteil seines NACHFAHR], wenn
  der [NACHFAHR Kind des VORFAHR] ist.
• Ein [VORFAHR ist Urgroßelternteil seines NACHFAHR], wenn
  eine [PERSON Elternteil des NACHFAHR] und der [VORFAHR Großelternteil der PERSON] ist.
  

Genauso könnte man sagen:

Ein [VORFAHR ist Vorfahr seines NACHFAHR], wenn

• der [VORFAHR ein Elternteil des NACHFAHR] ist
• eine [PERSON Elternteil des NACHFAHR] ist und der [VORFAHR ein Vorfahr dieser PERSON] ist.

vorfahr(VORFAHR,NACHFAHR) :- elternteil(VORFAHR,NACHFAHR).
vorfahr(VORFAHR,NACHFAHR) :- elternteil(PERSON,NACHFAHR), vorfahr(VORFAHR,PERSON).

Hierbei handelt es sich um eine rekursive Regel. Die erste vorfahr-Regel ist nicht-rekursiv, sie sorgt für die Terminierung der Rekursion. In der zweiten Regel befindet sich der rekursive Aufruf. So wie jeweils das Elternteil, Großelternteil, u.s.w. in der nachfolgenden Regel aufgerufen wurden, wird nun nur noch die vorfahr-Regel selbst wieder aufgerufen. Um dies zu veranschaulichen betrachten wir nochmal den Teilstammbaum.

Aufgabe 2

Gehe die Anfrage vorfahr(V,frank). anhand des Teilstammbaums schrittweise durch und fülle die Lücken in dem Dokument aus.

Aufgabe 3

Verwende den vollständigen Stammbaum der Halbgötter und erweitere ihn um die vorfahr-Regel.

a) Gib eine Anfrage an, um

• alle Vorfahren von Annabeth herauszufinden.
• alle Nachfahren von Hera zu finden.

b) Welche Ausgaben erwartest du? Überprüfe.

• vorfahr(zeus,jake).
• vorfahr(X,katie).

Aufgabe 4

Gib eine rekursive Regel nachfahr(NACHFAHR,VORFAHR). an.