Eine kleine und spaßige Teilaufgabe aus Programmieren hat mich heute ins grübeln gebracht. Das bringt mich jetzt dazu zur Eigenreflexion etwas darüber zu schreiben. Großer Vorteil an dieser Aufgabe ist, das sie sehr überschaubar bleibt und aus nur wenigen Zeilen Quellcode besteht.

Aufgabe war eine einfach-rekursive Funktion zu schreiben, die die n-te Fibonacci-Zahl berechnet. Anschließend soll diese in eine endrekusive und iterative (mit while und reduce) Variante transformiert werden. Die Funktion soll für alle natürlichen Zahlen einschließlich 0 gültig sein.

Als einfach-rekursive Funktion:

1
2
3
4
5
6

#Purpose: Fibonacci number of n.
#fibo ::= (n) :: Nat -> Nat
def fibo(n)
  check_pre(n.nat?)
  (n > 1 ? fibo(n - 1) + fibo(n - 2) : n)
end

Kurze Erklärung zu den zwei Funktionen von Außerhalb: Hier taucht ein check_pre() auf, dass bei false eine Exception schmeißt. Dies ist hier sehr wichtig, da negative Werte nicht definiert sind. Das n.nat? Prädikat prüft einfach, ob der Integerwert in den natürlichen Zahlen liegt.

Diese einfach-rekusive Funktion war schnell geschrieben, hat aber eine Laufzeit von ~2^n und daher lohnt sich eine Transformation in eine endrekursive Version mit einer Laufzeit von ~n deutlich. Hier wurde es dann spannend und ich musste etwas frickeln, denn es gibt zwei Akkumulatoren und die 0 soll eben auch definiert sein.

Als endrekursive Funktion:

1
2
3
4
5
6
7
8
9
10
11
12

#Purpose: Fibonacci number of n.
#fibo ::= (n) :: Nat -> Nat
def fibo(n)
  check_pre(n.nat?)
  (n == 0) ? 0 : fibo_(1, 0, n)
end
 
#fibo_ ::= (accu1,accu2,n) :: Nat x Nat x Nat -> Nat
def fibo_(accu1, accu2, n)
  res = accu1 + accu2
  (n > 2 ? fibo_(res, accu1, n - 1) : res)
end

Das Schwierigste daran ist aus meiner Sicht die zweifache Akkumulation. Weiterer großer Vorteil zur einfach-rekursiven Funktion ist der geringere Speicherverbrauch, vorausgesetzt es ist TCO aktiv. Ansonsten lohnt sich wiederum eine Transformation in eine Iteration, wobei diese leider imperativ arbeitet. Etwas blöd ist, dass die für die Fibonacci Reihe relativ unbrauchbare 0 der natürlichen Zahlen extra abgefangen werden muss.

Als Iteration mit while:

1
2
3
4
5
6
7
8
9
10
11
12
13
14

#Purpose: Fibonacci number of n.
#fibo ::= (n) :: Nat -> Nat
def fibo(n)
  check_pre(n.nat?)
  accu1 = 1
  accu2 = 0
  while (n > 1)
    res = accu1 + accu2
    accu2 = accu1
    accu1 = res
    n = n - 1
  end
  (n == 0 ? n : accu1)
end

Die Iteration mit while lässt sich (besonders bei nur einem Akkumulator) sehr einfach aus der endrekursiven Variante extrahieren. Direkt vor dem while werden die Akkumulatoren mit den Werten initialisiert, wie sie zu Beginn an die Hilfsfunktion (“fibo_”) gegeben werden. In der Schleife selbst bekommen sie den akkumulierten Wert neu zugewiesen anstatt als Parameter an die rekursiv aufgerufene Hilfsfunktion weiter gegeben zu werden. Das Endergebnis wird dann hinter der Schleife returned. Da wir in diesem Fall zwei Akkumulatoren haben und eine Iteration imperativ arbeitet, muss besonders darauf geachtet werden, dass die Addition der Akkumulatoren vor der Neuzuweisung stattfindet (hier über die Variable “res”). Die Rückgabe geht über “accu1″, der wie in der endrekursiven Variante die letzte Addition der Akkumulatoren enthält.

Als letzte Variante der Fibonacci Reihe kann man die Funktion in Ruby noch sehr kompakt über eine Iteration mit reduce (auch: “inject”) schreiben. Dabei arbeitet reduce auch imperativ, jedoch passiert alles intern. Auch diese Lösung ist bei zwei Akkumulatoren etwas tricky, weil reduce nur einen Akkumulator kennt. Um dies zu lösen wird der Akkumulator zu einem Array.

Als Iteration mit reduce:

1
2
3
4
5
6

#Purpose: Fibonacci number of n.
#fibo ::= (n) :: Nat -> Nat
def fibo(n)
  check_pre(n.nat?)
  (0..n).reduce([1,0]) {|(accu1, accu2), res| [accu2, accu1 + accu2]}[0]
end

Als persönlichen Favoriten sehe ich die Iteration mit reduce, wenn die entsprechende Sprache dies unterstützt, da sie sehr kompakt zu schreiben ist. Für andere Sprachen ist die endrekusive Variante besser geeignet. Leider sind beide nicht so leicht zu lesen .