Читать книгу Algorithmen und Datenstrukturen - Gunter Saake - Страница 75

Die Fakultätfunktion ist mathematisch wie folgt definiert:

x! = x(x − 1)(x − 2) … 2 · 1 für x > 0

Die bekannte rekursive mathematische Definition lautet 0! = 1 und x! = x · (x − 1)!. Das nahe liegende Problem bei dieser Definition ist die Behandlung negativer Eingabewerte.

Unsere erste Lösung überträgt die gegebene mathematische Gleichung direkt in den Formalismus der applikativen Algorithmen:

fac(x) = if x = 0 then 1 else x · fac(x − 1) fi

Die Bedeutung dieser Funktionsdefinition kann wie folgt angegeben werden:

Eine zweite Lösungsvariante versucht die Undefiniertheit im negativen Bereich zu vermeiden:

fac(x) = if x ≤ 0 then 1 else x · fac(x − 1) fi

Die Bedeutung ist nun:

Welche Lösung ist nun die bessere? Diese Frage lässt sich nicht einfach beantworten. Die erste Variante ist mathematisch korrekt, führt aber bei einer Eingabe von − 1 zu einer nicht abbrechenden rekursiven Berechnung – im praktischen Einsatz ein unschönes Verhalten. Die zweite vermeidet diesen Effekt, hält sich aber nicht an die Vorgabe der mathematischen Definition – allerdings ist das Ergebnis immer korrekt, wenn der Definitionsbereich der Fakultätsfunktion eingehalten wird.

Fibonacci-Zahlen

Ein weiteres bekanntes mathematisches Beispiel für Rekursion sind die Fibonacci-Zahlen. Entwickelt wurde diese Zahlenreihe, um zum Beispiel die Progression bei der Vermehrung von Tieren darzustellen. Ein vereinfachtes Modell wäre folgendes:

Fruchtbare Kaninchen

Am Anfang gibt es ein (Kaninchen-)Paar. Jedes Paar wird erst im zweiten Monat vermehrungsfähig, danach zeugt es jeden Monat ein weiteres Paar.

Dieses Verhalten kann direkt in die Definition der Fibonacci-Zahlen umgesetzt werden: