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
oder alternativ: 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 |
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 |
Ü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 |