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.
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.
Quellen
- [1]: Teilstammbaum der Halbgötter - Urheber: MB - Lizenz: inf-schule.de
- [2]: Rekursion - Urheber: MB - Lizenz: inf-schule.de