Verzweigungsfaktoren
Wenn man mit rekursiven Funktionen arbeitet, kann es manchmal sinnvoll sein, dieselbe Funktion mehrmals mit unterschiedlichen Parametern aufzurufen. Ein typisches Beispiel dafür ist die Berechnung der n-ten Fibonacci-Zahl über eine rekursive Funktion. Diese könnte folgendermaßen aussehen:
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)Hier werden für jedes Argument
n zwei rekursive Aufrufe der Funktion fib mit den Parametern n-1 und n-2 ausgeführt.Herausforderung – Rekursive Fibonacci
Zählen Sie, wie oft die rekursive Funktion
fib aufgerufen wird.Eingabe
Die Eingabe besteht aus einer einzigen Ganzzahl
n (0 ≤ n ≤ 20).Ausgabe
Das Programm soll ausgeben, wie oft die Funktion
fib aufgerufen wurde.Beispiele
Eingabe | Ausgabe |
0 | 1 |
1 | 1 |
2 | 3 |
5 | 15 |
6 | 25 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB