Recursion Problem . Please Explain me the output of this recursion program in python.

Question

Python Program:

def fib(x):
if x == 0 or x == 1:
return 1
else:
a = fib(x-1) + fib(x-2)
print(fib(x-1),"+",fib(x-2))
return a

print(fib(4))

Output:
1 + 1
1 + 1
2 + 1
1 + 1
1 + 1
1 + 1
2 + 1
1 + 1
3 + 2
5

Guys please explain me this program.
Thanking you greatly :)

Answer 1

The problem in your code is that you return 1 in both cases when number is equal to 0 and 1 which is wrong. According to the formula when number equals 0 you should return 0 and if it equals 1 you should return 1.

So you code should look like this:
def fib(x):
if x==0 or x==1:
return x #note that I return x instead of 1
else:
a = fib(x-1) + fib(x-2)
print(fib(x-1),"+", fib(x-2))
return a

print(fib(4))

Answer 2

Ah sorry, I thought you are confused with the answer.

So fib method calls itself until it reaches return
fibonacci(5)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(4)
fibonacci(2)
fibonacci(0)
fibonacci(1)
fibonacci(3)
fibonacci(1)
fibonacci(2)
fibonacci(0)
fibonacci(1)

Answer 3

@Suhrob yeah I also tht like tht only sir if recursion flows like it means output will be 1 + 1 = 2.
But here it is 5 that is only I cann't understand sir.
Thanking you very much...

Answer 4

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))

Output:5

This is the real piece of code buddy given in SoloLearn in recursion topic.
I m just confused with this so can u explain bro?