Aufgabe:
b) Betrachten Sie die Funktion fibonaiv, welche auf naive Weise die \( n \) -te Fibonacci-Zahl fib \( (n) \) (siehe Beispiel 4.19 im Skript) rekursiv berechnet:
def fibonaiv(n):
if n<=2:
return 1
else:
return ( fibonaiv(n-1) + fibonaiv(n-2)
i) Geben Sie den Rekursionsbaum Baum(5) für den Aufruf fibonaiv(5) in grafischer Darstellung an. (Ohne Begründung) Ist Baum(5) ein Binärbaum? Ist er ein voller Binärbaum? Ist er ein vollständiger Binärbaum?
ii) Zeigen Sie durch vollständige Induktion: Für jedes \( n \in \mathbb{N}_{>0} \) hat Baum(n) für den Aufruf fibonaiv (n) genau fib \( (n) \) Blätter.
Ich weiß wie ich eine vollständige Induktion mache und ich weiß auch was die Fibonacci-Zahlen machen. Ich weiß nicht, ob ich die Aufgabe nicht komplett verstanden habe oder ob ich einfach nur kein Ansatz finde. Aufjedenfall bräuchte ich unbedingt einen Ansatz oder einen Denkanstoß für die b)ii).
