Why is the Output 5?

Question

def fb(n):
if n == 0:
return 0
if n == 1:
return 1
else:
return(fb(n-1) + fb(n-2))
print(fb(5))

I can normally play with the code and figure it out, which feels great, but I just can't figure this one out. I'd be grateful for any help!

Answer 1

@Aaron , Tomer , Stephane
//here is the easy way to think
lets see ... 👍
//accn to definition of funcn , term no3 or greater will be sum of previous two terms
fb (0)=0 //defined in funcn
fb (1)=1 //defined in funcn
fb (2)=1
fb (3)=2
fb (4)=3
fb (5)=5
//looks easy , when think from definition of funcn ... right
//👉this way is helpful for making hard-recursion in seconds👈

Answer 2

For fb(5) this will happen: (read the first part before | and then the second part)
fb(5) -> return fb(4)+fb(3) | fb(4)=3, fb(3)=2, so return 3+2=fb(5)=5
fb(4)-> return fb(3)+fb(2) | fb(3)=2 fb(2)=1 so return 2+1=3=fb(4)
fb(3)-> return fb(2)+fb(1) | fb(1)=1 f(2)=1 so return 1+1 -> return 2 =fb(3)
fb(2)-> return fb(1)=1 + fb(0)=0-> return 1
hope this is clear to you.

Answer 3

You created a method that calls itself twice... so it's hardly possible to predict any output without calculating every single step of the program