Prolog eLearning
Tutorial

3: Rekursion

Zu den Aufgaben Folien ansehen Musterlösungen herunterladen
  • Ein wichtiges Konzept für das Lösen von Aufgaben bzw. für die Definition mächtiger Prädikate ist die Rekursion.
  • Ein Prädikat ist rekursiv definiert, wenn in einer der definierenden Regeln das Prädikat im Regelkörper aufgerufen wird.
  • Rekursion ist eine Problemlösungsstrategie. Die Grundidee ist das Zurückführen einer allgemeinen Aufgabe auf eine einfachere Aufgabe derselben Klasse (Schleifen).
  • Rekursion ermöglicht es kompakte Prädikatsdefinitionen zu schreiben und Redundanz zu vermeiden.

rekursive Prädikate in Prolog

  • Ein Prädikat ist rekursiv definiert, wenn in einer der definierenden Regeln das Prädikat im Regelkörper aufgerufen wird.
  • Das Prädikat teurer/2 ist rekursiv definiert.

rekursive Definition von teurer/2

kostet_etwas_mehr(eis,lolli).
kostet_etwas_mehr(burger,eis).
kostet_etwas_mehr(schnitzel,burger).
kostet_etwas_mehr(sushi,schnitzel).
teurer(X,Y):-
    kostet_etwas_mehr(X,Y).
teurer(X,Y):-
    kostet_etwas_mehr(X,Z),
    teurer(Z,Y).

rekursive Definitionen

Beispiel: natürliche Zahlen

  • 0 ist eine natürliche Zahl. (Ankerregel)
  • Wenn n eine natürliche Zahl ist, dann ist auch der Nachfolger von n (also n + 1) eine natürliche Zahl. (rekursive Regel)
  • Nichts sonst ist eine natürliche Zahl. (Ausschlussregel)

Beispiel: transitive Relation “Vorfahr”

A ist ein Vorfahr von B, wenn

  • A ein Elternteil von B ist. (Ankerregel)
  • wenn A ein Vorfahr von C und C ein Elternteil von B ist. (rekursive Regel)
  • Sonst ist A kein Vorfahr von B. (Ausschlussregel)

nicht rekursive Definition von teurer/2

kostet_etwas_mehr(eis,lolli).
kostet_etwas_mehr(burger,eis).
kostet_etwas_mehr(schnitzel,burger).
kostet_etwas_mehr(sushi,schnitzel).
teurer(X,Y):-
    kostet_etwas_mehr(X,Y).
teurer(X,Y):-
    kostet_etwas_mehr(X,A),
    kostet_etwas_mehr(A,Y).
teurer(X,Y):-
    kostet_etwas_mehr(X,A),
    kostet_etwas_mehr(A,B),
     kostet_etwas_mehr(B,Y).
teurer(X,Y):-
    kostet_etwas_mehr(X,A),
    kostet_etwas_mehr(A,B),
    kostet_etwas_mehr(B,C),
    kostet_etwas_mehr(C,Y).

deklarative und prozedurale Bedeutung einer Wissensbasis

deklarative Bedeutung

  • Unter der deklarativen Bedeutung versteht man die Bedeutung, die ‘gemeint’ oder die ‘ausgedrückt’ ist, wenn man die Wissensbasis als Menge logischer Aussagen liest.
  • Die deklarative Bedeutung eines Prologprogramms kann extensional als die Menge aller Aussagen definiert werden, die sich logisch aus der Theorie der Wissensbasis (sprich Sammlung von logischen Aussagen) ableiten lassen.

prozedurale Bedeutung

  • Unter der prozeduralen Bedeutung versteht man die Bedeutung, die sich daraus ergibt, was Prolog mit einer Wissensbasis ‘tut’.
  • Die Prozedurale Bedeutung eines Prologprogramms kann extensional als die Menge aller Anfragen (Aussagen) definiert werden, für die der Prolog-Interpreter eine Variablenbelegung findet, die zu der Ausgabe true. führt.

Beispiel: Definition natürlicher Zahlen

Natürliche Zahlen

  • 0 ist eine natürliche Zahl. (Ankerregel)
  • Wenn n eine natürliche Zahl ist, dann ist auch der Nachfolger von n eine natürliche Zahl. (rekursive Regel)
  • Nichts sonst ist eine natürliche Zahl. (Ausschlussregel)

Wir verwenden succ/1 zur Kodierung natürlicher Zahlen: 

0 => 0
1 => succ(0)
2 => succ(succ(0))
3 => succ(succ(succ(0)))
...

Ziel: Ein Prädikat numeral/1, welches überprüft ob das Argument eine natürliche Zahl in der succ-Darstellung ist. 

% Ankerklausel: 0 ist eine Zahl
numeral(0).
% rekursive Klausel: Der Nachfolger einer Zahl ist eine Zahl
numeral(succ(X)) :- numeral(X).

kann zur Generierung von Zahlen genutzt werden: 

?- numeral(X). X=0;
X = succ(0) ;
X = succ(succ(0)) ;
X = succ(succ(succ(0))) ;
X = succ(succ(succ(succ(0)))) ;
X = succ(succ(succ(succ(succ(0))))) ;
X = succ(succ(succ(succ(succ(succ(0)))))) ;
X = succ(succ(succ(succ(succ(succ(succ(0))))))) ;
X = succ(succ(succ(succ(succ(succ(succ(succ(0)))))))) ;
X = succ(succ(succ(succ(succ(succ(succ(succ(succ(0))))))))) ; ...

prozedural = deklarativ

Konsequenz für die Prologprogrammierung:

  • zunächst sollte man immer das Problem beschreiben (deklarativ),
  • anschließend muss man sich Gedanken über die Arbeitsweise (prozedural) des Prolog-Interpreters machen und das Programm gegebenenfalls anpassen.

Definieren harmloser rekursiver Prädikate:

  • Rekursive Prädikate benötigen immer mindestens zwei Klausel: rekursive Klausel plus Anker- oder Ausstiegsklausel.
  • Die Ankerklausel sollte immer vor der rekursiven Klausel stehen (sonst droht eine Endlosschleife).
  • Im Regelkörper der rekursiven Klausel ist es oft sinnvoll, den rekursive Aufruf ans Ende zu setzen.

Beispiel: Addition natürlicher Zahlen

Ziel: Ein Prädikat add/3, welches drei Zahlen in der succ-Darstellung als Argument nimmt.

Das dritte Argument soll die Summe der beiden ersten sein.

  • Ankerklausel: Wenn das erste Argument 0 ist, dann ist das zweite Argument gleich dem dritten Argument.
  • Rekursive Klausel: Wenn die Summe von X und Y gleich Z ist, dann ist die Summe von succ(X) und Y gleich succ(Z). 
% Ankerklausel
add(0,Y,Y).
% rekursive Klausel
add(succ(X),Y,succ(Z)):-
    add(X,Y,Z).

Zurück zur prozeduralen und deklarativen Bedeutung

Zur Erinnerung: Bei der Beweisführung arbeitet sich Prolog

  • durch die Wissensbasis von oben nach unten,
  • innerhalb der einzelnen Klauseln von links nach rechts durch die Teilziele. 
et(albert,kevin).
et(lena,albert).
et(marie,lena).
vorfahr1(X,Y):- et(X,Y).
vorfahr1(X,Z):-
    et(X,Y),
    vorfahr1(Y,Z).
vorfahr2(X,Z):-
    et(X,Y),
    vorfahr2(Y,Z).
vorfahr2(X,Y):- et(X,Y).
vorfahr3(X,Y):- et(X,Y).
vorfahr3(X,Z):-
    vorfahr3(Y,Z),
    et(X,Y).
vorfahr4(X,Z):-
    vorfahr4(Y,Z),
    et(X,Y).
vorfahr4(X,Y):- et(X,Y).

Die Reihenfolge der Klauseln und der Teilziele innerhalb der Klauseln beeinflusst ihre prozedurale Verarbeitung!

Wiederholung: rekursive Prädikate

Ziele: Rekursive Prädikate,

  • die nicht zu Endlosschleifen führen,
  • die möglichst früh terminieren,
  • die mit offenen Variablen aufgerufen werden können.

Definieren harmloser rekursiver Prädikate:

  • Rekursive Prädikate benötigen immer mindestens zwei Klausel: rekursive Klausel plus Anker- oder Ausstiegslkausel.
  • Die Ankerklausel sollte immer vor der rekursiven Klausel stehen (sonst droht Endlosschleife).
  • Im Regelkörper der rekursiven Klausel ist es oft sinnvoll, den rekursive Aufruf ans Ende zu setzen.