3. Rekursionen
fact (Version2) Aus der Mathematik ist bekannt, dass man die Fakultät rekursiv definieren kann. Wir wollen diese Idee auch in WinHugs umsetzen. Die Funktionen speichern wir in der Datei Rekursionen.hs ab, die wir später um weitere Rekursionen erweitern können.

module Rekursionen where


fact :: Integer -> Integer
fact 0 = 1
fact n = n* fac (n-1)
 

oder alternativ:

fact :: Integer -> Integer

fact n | n==0 = 1
       | otherwise = n*fact (n-1)

Wie gewohnt wird in der ersten Zeile der Funktionsdefinition die Typen für Eingabe und Ausgabe festgelegt. Die Funktionalität wird nun in zwei Zeilen festgelegt. Ist der Übergabewert 0, so wird der Fakultätswert auf ein gesetzt. Ist der Übergabewert nicht 0 so versucht der Interpreter den Wert über die zweite Zeile zu ermitteln. Dort erkennen wir den rekursiven Aufruf der Funktion fact. Der rekursive Abstieg ist deutlich: soll z.B. der Wert fact 3 bestimmt werden, ermittelt der Interpreter

fact 3 = 3 * fact 2
  fact 2 = 2 * fact 1
    fact 1 = 1 * fact 0
      fact 0 = 1
    fac 1 = 1 * 1 = 1
  fact 2 = 2 * fact 1 = 2
fact 3 = 3 * fact 2 = 6

 

ggT Die Formulieren des rekursiven Algorithmus' zur Berechnung des ggT zweier Zahlen sieht so aus. Der

ggT(a,a) = 1,
ggT(a,b) = ggT(a-b,b) falls a>b und
ggT(a,b)=ggT(b-a,a) sonst (also b>a).
 
Download:
Kapitel03.hs

Diese Formulierung ist vom Mathematikunterricht her bekannt und kann fast 1 zu 1 in Haskell übersetzt werden:

ggT :: Integer -> Integer -> Integer

ggT a b |a==b = a
        |a>b  = ggT (a-b) b
        |a<b  = ggT (b-a) a


Übung 1

Erweitern Sie die Datei
Kapitel03.hs um die Funktion fib. fib n soll die n-te Fibonaccizahl berechnen (n aus N). Finden Sie zunächst die rekursive Beschreibung der Erzeugung von Fibonacci-Zahlen.

1, 1, 2, 3, 5, 8, 13,...

 

Übung 2 Erweitern Sie Rekursionen.hs um die Funktion kgV, die allerdings nicht rekursiv ist, aber auf ggT zurückgreift.

 

Lösungen zu den Lösungen
 

(C) 2005 www.pohlig.de