Recursion Python

Question

Someone please help me in python recursions... I am feeling so bad bcz i can't understand this topic properly

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

https://code.sololearn.com/c0urSqZdqOjU/#py

Answer 1

In the recursion we have base case in the if part and the recursive part in the else case
So here we passed 4
In the if part since it fails ,it enters into else case where we have
fib(4-1)+fib(4-2) // x =4(it executes)
So we have fib(3)+fib(2) // again it is calling the function fib()
Again fails with if case
Else:
Fib(3)=fib(2)+fib(1)
Fib(2)=fib(1)+fib(0)
Addition of both
=> fib(3)+fib(2) = Fib(2)+fib(1)+fib(1)+fib(0) (equation 1)

Again its calling function back recursively so for fib(1) and fib(0) it will be replaced with 1 as
Eqn 1=>Fib(2)+1+1+1(equation 2)
Fib(2) enters else:
So,fib(1)+fib(0)+1+1+1
Same again call back
Hence
Eqn 2 =>1+1+1+1+1 =5

Answer 2

Try to make binary tree under each statement and write the appropriate result beneath it.
Happy coding
In nut shell when the function terminate it moves where is called then execution takes place😊

Answer 3

So entered value is 4 , now function returns fib(4-1)+fib(4-2)=fib(3)+fib(2)
Now seperate function runs for each fib, one with argument 3 and other with 2
So fib(3) returns fib(3-1)+fib(3-2)=fib(2)+fib(1) and fib(2) returns fib(2-1)+fib(2-2)=fib(1)+fib(0)

Now if x==0 or x==1,1 is returned without calling the function
so again four times fib function is called with argument 2,1,1,0
For the function with argument 1,1,0 , function isn't called again and only 1 is returned ,so we have 3 1's now ,

fib(2)+fib(1)+fib(1)+fib(0) now becomes:
fib(2)+1+1+1
let's breakdown the last function, fib(2) returns fib(1)+ fib(0)

So now we have fib(1)+fib(0)+1+1+1=1+1+1+1+1=5 , hopefully it clears up all your doubt ,

Answer 4

to better understand look this :

fib(4):
fib(3) + fib(2)
fib(3) ---> (fib(2) + fib(1)) and fib(2) ---> (fib(1) + fib(0))
fib(2) ----> (fib(1) + fib(0)) and totally remains:
fib(1) + fib(0) + fib(1) + fib(1) + fib(0)
1 + 1 + 1 + 1 + 1

Answer 5

Ok, that's all fine and well, but how do we get the output of each iteration of the recursive function?

I've tried dropping print statements in different places, but the best result that I've gotten is when the function prints out the n-th number, as requested by an input value...

I'm probably missing something simple, but right now I'm coming up blank