please explain the code given in the description ?

Question

What is the result of this code?
def fib(x):
if x == 0 or x == 1:
return 1
else:
return fib(x-1) + fib(x-2)
print(fib(4))

Answer 1

Fib(4)
|
_______/ \________
| + |
Fib(3) Fib(2)
| |
_______/ \____ ____/ \_______
| + | | + |
Fib(2) Fib(1) Fib(1) Fib(0)
_______/ \_______
| + |
Fib(1) Fib(0)

Fib(4) = Fib(1) + Fib(0) + Fib(1) + Fib(1) + Fib(0)
= 1 + 1 + 1 + 1 + 1
= 5

Implements function
-- 1 ,if n=0 or n=1
|
T(n) = ---|
|
-- T(n-1)+T(n-2) , if n>1

Answer 2

Wow, I salute your effort Prokopios Poulimenos !

Answer 3

Wow, that must have taken a while! :)