Rekursion der Fibonacci -Sequenz ⇐ Python

[Anonymous]

Ich brauche Hilfe beim Verständnis der Verarbeitung, die hier passiert. Sagen wir also, ich nenne FIB (5) Ich möchte, dass der Fibonacci 5 8 ist. Aber mein Gehirn beim Versuch, den Algorithmus zu verstehen, sagt, dass es nicht ist. So denke ich (fälschlicherweise): < /p>

Code: Select all

return fib(4) + fib(3) // Stack frame 1
return fib(3) + fib(1) // Stack frame 2

Jetzt ist x 1 Fib (1) , die bedingte Anweisung, wenn x == 0 oder x == 1: die Rekursion beendet. Was nach meiner Logik 3+1+4+3 werden würde. Bitte korrigieren Sie meine fehlerhafte Logik. < /P>

Code: Select all

def fib(x):
"""assumes x an int >= 0
returns Fibonacci of x"""
assert type(x) == int and x >= 0
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)