Folien zur Vorlesung

[.pdf]

Inhalt

• Grundlegende Konzepte
  • Abstraktion
  • Iteration
  • Rekursion
  • Rekursive Funktion
• Formen von Rekursion:
  • Einfache Rekursion
  • Mehrfachrekursion
  • Binäre Rekursion
  • Primitive Rekursion
  • Endrekursion
• Beispiele:
  • Die Fakultätsfunktion
  • Die McCarty 91-er Function
  • Türme von Hanoi
  • Die Fibonacci-Folge
  • Lineare Suche
• Transformationen zur Rekursion:
  • Entfernung von Endrekursion
  • Verwendung von einem Akkumulator
  • Entfernung von Rekursion

Fragestellungen aus der Vorlesung

• Was ist Rekursion inbesondere bezogen auf Funktionsdefinitionen?
• Wie wird Rekursion in einer Programmiersprache ausgedrückt?
• Welche verschiedenen Formen von Rekursion gibt es?
• Was sind die Kosten rekursiver Programmierung?
• Wie kann Rekursion beseitigt und etwa durch Iteration ersetzt werden?

Empfehlungen zur Nachbereitung

• Ausprobieren der Beispiele aus der Vorlesung
• Beweis der Eigenschaft der McCarty 91-er Function
• Studium der linearen Suche (mit Verwendung von Feldern)