Informatikmaterialien  von Tino Hempel

Startseite | Informatik | Physik | Mathematik | Sonstiges | | Inhalt | Vorherige Seite | Nächste Seite |

	Richard-Wossidlo-Gymnasium Ribnitz-Damgarten Fachbereich Informatik

Rekursion I
(unter Verwendung von Rekursionen in Prolog und allgemein)

Rekursionen gehören zu den Besonderheiten einer höheren Programmiersprache.  

Definition

Objekte, die sich selbst enthalten sind rekursiv.

Beispiele: 

• Bild im Bild 

• Matroschkas 

• Schachtel in Schachtel

• Spiegel im Spiegel

Ein Problem rekursiv lösen heißt, es auf eine einfachere Version seiner selbst zurückzuführen. Dies geschieht solange, bis ein unmittelbar lösbarere Anfang erreicht ist.

Beispiele:

• Schachtelsätze: 
  Die, die die Personen, die die Schilder, auf denen "Bekleben verboten" stand, beklebt haben, anzeigen, erhalten eine Belohnung.
  ... und nicht nur von uns, sondern auch von unseren Vätern, und von unseren Väter Vätern, und von unseren Väter Väter Vätern, ...

• Berechnung eines Gliedes einer mathematischen Folge mit a(0) = 1 und a(n) = 2 + a(n-1) mit n = 0...100; gesucht: a(5)
  Lösung: a(5) = 2 + a(4) = 2 + (2 + a(3)) = 2 + (2 + (2 + a(2))) = 2 + (2 + (2 + (2 + a(1)))) = 2 + (2 + (2 + (2 + (2 + a(0))))) = 11

Eine Regel heißt rekursiv, wenn das Prädikat im Regelkopf auch im Regelkörper vorkommt.

Bemerkungen:

• Um eine Rekursion in PROLOG darzustellen, werden i. allg. zwei Klauseln benötigt. Die erste Klausel stellt die Abbruchbedingung als Fakt dar, die zweite Klausel ist die rekursiv geschriebene Regel.

• Es ist stets dafür Sorge zu tragen, dass die Rekursion abbricht.

Beispiel: 

Es soll ein Prädikat zur Bestimmung der Vorfahren in einer Familienbeziehung angegeben werden. Dazu erklären wir vorfahr_von(X,Y) wie folgt: X ist ein Vorfahre von Y, falls X ein Elternteil von Y ist. Damit finden wir aber nur die direkten Vorfahren. Nun nutzen wir die Rekursion zur Ermittlung weiterer Vorfahren durch die Formulierung: X ist ebenfalls ein Vorfahre von Y, falls X ein Elternteil von Z ist und Z ein Vorfahre von Y.

vorfahre_von(X,Y):- elternteil(X,Y).
vorfahre_von(X,Y):- elternteil(X,Z),vorfahre_von(Z,Y).

---

zur Startseite

© Tino Hempel 1997 - 2002 Letztes Update 08.2002

Im Web vertreten seit 1994. Eine Internet-Seite aus dem Angebot von Tino Hempel. Für alle Seiten gilt der  Haftungsausschluss/Disclaimer.