Haskell - Rekursion

Haskell - Rekursion

Während es in imperativen Programmiersprachen Kontrollstrukturen zur Wiederholung von Anweisungen -  Schleifen - gibt, besteht bei Haskell die einzige Wiederholungsmöglichkeit darin, eine Funktion rekursiv zu definieren.

  1. Rekursionsschritt:Dabei wird die Funktion im Funktionskörper noch einmal mit veränderten Paramter-Werten aufgerufen. Das würde normalerweise unendlich lange dauern, da dieser Aufruf immer wieder erfolgt!
  2. Rekursionsanker - Abbruch des rekursiven Aufrufs:Deshalb muss zwingend eine Abbruchbedingung definiert  werden, der sogenannten Rekursionsanker. Dieser kann durch Mustererkennung (Pattern Matching) oder andere Verfahren realisiert werden.

BeispielDer jungen Carl Friedrich Gauß entdeckte die Summen-Formel als neunjähriger Schüler (wieder[1]), indem er die Aufgabenstellung „Addiere alle Zahlen von 1 bis 100“ zur Überraschung seines Lehrers in Sekundenschnelle löste. Wir hingegen verfügen nicht über die Fähigkeiten des jungen Gauß und auch nicht über seine Summenformel, sondern lösen als Informatiker dieses Problem anders - mit Hilfe der Rekursion:

summe :: Int−>Int

summe 0 = 0                -- Rekursionsanker   [0]

summe n = n + summe (n−1)  -- Rekursionsschritt [1]

Rekursionsschritt: Aufruf der definierten Funktion auf der rechten Seite des Gleichheitszeichens. Die rechte Seite wird auch Funktionskörper genannt.

Übung mit Stift und Papier:Auswertung dieser Funktion beim Aufruf von summe 4.

Weiteres Material zum Durchlesen / Durcharbeiten

  • Thema Rekursion bei inf-schule.de. Die Inhalte beziehen sich auf die imperative Programmierung (Python) sind aber inspirierend, nachvollziehbar und bieten Ideen für eine eigene Implementierung rekursiver Funktion in Haskell.
  • Material aus dem Unterricht bzw. in der übergeordneten Webseite zur Funktionalen Programmierung mit Haskell

[1] Diese Summenformel war bereits in der vorgriechischen Mathematik bekannt.