Übung 3:

1. Implementieren Sie zwei Funktionen zur Berechnung der n-ten Fibonacci-Zahl, die sich dazu selbst aufrufen. (Die Folge ist definiert als f₀=0, f₁=1, f_n=f_n-1+f_n-2.) Implementieren Sie eine Version für einen rekursiven Prozeß (erst aufrufen, dann berechnen) und eine für einen iterativen Prozeß (erst berechnen, dann aufrufen). Bis zu welchem Wert funktioniert die Berechnung? Wie unterscheiden sich die beiden in der Laufzeit?
   Tips:
   • Verwenden Sie einen Datentyp mit mindestens 64 Bit Breite und (wenn möglich) ohne Vorzeichen, oder verwenden Sie eine Sprache, in der die Größe von Zahlen nicht (spürbar) begrenzt ist.
   • Am besten schreiben Sie zwei Programme fib-iter und fib-rek, denen man beim Aufruf mitgibt, die wievielte Fibonacci-Zahl sie berechnen sollen. Dann kann man mit dem Befehl time sehr einfach die Zeit messen.
   • Wenn die Zahlen in ihrer Größe begrenzt sind, ist eine Überlaufprüfung sinnvoll.