Übungen 3: Aufrufbäume

Die Fibonacci-Funktion (auch als Fibonacci-Folge bezeichnet) ist definiert als:

$$f(n)=$$ { 0 wenn n = 0 1 wenn n = 1 f(n−1)+f (n−2) sonst Die ersten Werte der Fibonacci-Funktion sind 0, 1, 1, 2, 3, 5, 8, 13, … Die Definition kann einfach in eine rekursive Methode übersetzt werden: fib(n: int): int wenn n ≤ 1: gib n zurück sonst: gib fib(n-1) + fib(n-2) zurück (a) Geben Sie die vier Werte der Fibonacci-Folge an, die auf das Folgenglied 13 folgen. (b) Stellen Sie die ausgeführten Methodenaufrufe bei der Ausführung von fib(4) als Baum dar. © Begründen Sie, warum die Anzahl der Methodenaufrufe für fib(n) weniger als 2 beträgt. n+1 (d) Implementieren Sie eine Methode fibIterativ(n: int): int, die dasselbe Er- gebnis wie fib berechnet, die aber ohne Rekursion arbeitet.