Aufgabe 2:  Führen Sie einige Messungen der Laufzeit der naiven rekursiven Implementierung der Fibonacci-Funktion fib(n) für verschiedene n durch.

Aufgabe 3:  Programmieren Sie in Python eine endrekursive Version der Fibonacci-Funktion. Stellen Sie zunächst ein paralleles Iterations­schema für die Berechnung der Fibonacci-Zahlen auf. Gehen Sie anschließend nach der Methode vor, die aus einem Iterations­schema eine endrekursive Funktion erzeugt.

Bemerkung: Eine endrekursive Funktion hat stets die Rekursions­breite 1 (im Gegensatz zur naiven rekursiven Implementierung der Fibonacci-Funktion).

Aufgabe 4:  Implementieren Sie die rekursive Definition der schnellen Exponentiation modulo n:

me mod n  =

1     falls e = 0 me-1 · m mod n      falls e ungerade (me/2)2 mod n     falls e gerade

Berechnen Sie 2⁹⁹⁹ mod 7.