Haskell - Rekursion

Haskell - Rekursion

Während es in anderen Programmiersprachen verschiedene Schleifen gibt, ist bei Haskell die einzige Wiederholungsmöglichkeit die Rekursion.

  1. Rekursionsschritt:
    Dabei wird die Funktion im Funktionskörper noch einmal mit einem Vorgänger aufgerufen. Das würde normalerweise unendlich lange dauern, da es immer einen Vorgänger gibt.
  2. Rekursionsanker:
    Deshalb muss zwingend eine Abbruchbedingung definiert  werden, der sogenannten Rekursionsanker. Dieser kann durch Mustererkennung (Pattern Matching) oder andere Verfahren realisiert werden.

Beispiel
Der 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, z.T. 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.

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