Rekursion in Prolog
Prädikate können rekursiv definiert werden, d.h. in einem Prädikat kann es selbst wieder auftauchen
% Rekursionsanker: Eltern sind direkt Vorfahren
ancestor(A,B) :- parent(A,B).
% Rekursionsschritt: Vorfahren können beliebig viele Generationen entfernt sein
ancestor(A,B) :- parent(A,A_B), ancestor(A_B,B).
➤ Prolog wird das Prädikat so oft in sich selbst einsetzen bis eine gültige Belegung gefunden ist.
Regeln für Rekursion
Nicht-Rekursive Klauseln zuerst!
- Erinnerung: Tiefensuche im Lösungsbaum.
- Es werden die Klauseln nacheinander von oben nach unten auf Unifizierbarkeit geprüft
- Steht die rekursive Klausel oben, ergibt sich ein unendlicher Lösungsbaum bevor der Rekursionsanker geprüft wird
Innerhalb einer Klausel: Nicht-rekursive Literale vor rekursivem Literal!
- So wird sichergestellt, dass Manipulationen an den Übergabewerten vor dem Rekursionsschritt geschehen
Zyklen in den Daten (Graph):
- Keine Zyklen innerhalb eines Prädikats!
- Besuchte Knoten in weiterem Parameter „merken“ (siehe nächste Folie)
Datenaustausch zwischen Rekursionsschritten
Wenn zwischen den Rekursionsschritten Datenaustausch nötig ist, kann dies über Variablen geschehen.
- Akkumulator: Zwischenrechnungen werden weiter nach „unten“ gegeben.
- Ergebnisvariable: Im Rekursionsanker wird das Ergebnis mit dieser Variable verknüpft.
cntAncestor(A,B,Cnt,Erg) :- parent(A,B), Erg = Cnt.
cntAncestor(A,B,Cnt,Erg) :- parent(A,A_B), Cnt1 is Cnt+1,
cntAncestor(A_B,B,Cnt1,Erg).
Anfrage:
?- cntAncestor(shmi, luke, 1, Erg).
Erg = 2
- Cnt muss mit dem Startwert (1) initialisiert werden, für Erg soll eine Belegung gefunden werden.
- In jedem Rekursionsschritt wird dieser Zähler (Cnt) inkrementiert.
Alternative Umsetzung der Rekursion
Setzen des Startwerts für Erg im Rekursionsanker.
cntAncestor2(A,B,1) :- parent(A,B).
cntAncestor2(A,B,Erg) :- parent(A,A_B),
cntAncestor2(A_B,B,Erg1), Erg is Erg1 + 1.
Erg is Erg1 + 1: Berechnung des Ergebnisses auf dem Weg nach „oben“.
Anfrage:
?- cntAncestor2(shmi, luke, Erg).
Erg = 2