Definieren Sie eine rekursive Funktion fib mit einem Parameter n,
die die n-te Fibonacci-Zahl berechnet. Es soll also fib(0) = 0,
fib(1) = 1 und fib(n+2) = fib(n+1) + fib(n)
gelten. Veranschaulichen Sie die Auswertung des Aufrufs fib(3)
analog zur obigen Auswertung des Aufrufs factorial(3).
Definieren Sie eine rekursive Python-Funktion binary mit einem Parameter n, die die Binärdarstellung der Zahl n als Zeichenkette aus Nullen und Einsen zurückliefert. Gehen Sie davon aus, dass als Argument eine nicht negative ganze Zahl übergeben wird. Zur Konvertierung zwischen Zahlen und Zeichenketten können Sie die Funktionen int und/oder str verwenden. Bei der Suche nach einer Idee für einen rekursiven Berechnungsprozess hilft vielleicht die Beobachtung, dass die Binärdarstellung 110 der Zahl 6 die Binärdarstellung 11 der Zahl 3 enthält.
Dokumentieren Sie die Ausführung des Aufrufs binary(6), indem Sie die Auswertung aller binary-Aufrufe als eigerückte Nebenrechnungen notieren.
Wie viele binary-Aufrufe werden bei der Auswertung von binary(n) in Abhängigkeit von n ausgeführt?
Geben Sie rekursive Definitionen für die Funktion from_to aus einer früheren Aufgabe an. Zur Erinnerung: from_to erzeugt eine aus Zahlen bestehende Liste anhand übergebener Grenzen (z.B. from_to(4,7) == [4,5,6,7]).
Überlegen Sie sich eine geeignete Abbruchbedingung und geeignete Argumente für rekursive Aufrufe. Geben Sie alternative Definitionen an, wenn Sie unterschiedliche Ideen für rekursive Aufrufe haben, und dokumentieren Sie die Auswertung jeweils mit Hilfe eingerückter Nebenrechnungen.