I need some help in understanding the processing that happens here, so let´s say I call fib(5) I want the fibonacci 5, which is 8. But my brain in trying to understand the algorithm says it´s not. This is how i (wrongly) think:
return fib(4) + fib(3) // Stack frame 1
return fib(3) + fib(1) // Stack frame 2
now cause x is 1 fib(1), the conditional statement if x == 0 or x == 1: causes the recursion to end. Which according to my logic would become 3+1+4+3. Please correct my faulty logic.
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)
Here is the full expansion of what happens:
fib(5) expands to fib(4)+fib(3)
fib(4) expands to fib(3)+fib(2)
fib(3) expands to fib(2)+fib(1)
fib(2) expands to fib(1)+fib(0)
fib(1) evaluates to 1
fib(0) evaluates to 1
fib(1) evaluates to 1
fib(2) expands to fib(1)+fib(0)
fib(1) evaluates to 1
fib(0) evaluates to 1
fib(3) expands to fib(2)+fib(1)
fib(2) expands to fib(1)+fib(0)
fib(1) evaluates to 1
fib(0) evaluates to 1
fib(1) evaluates to 1
If you count the ones, you get 8 as the answer.