+ 3

Recursion Python

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

27th Jul 2020, 10:01 AM
Natu
Natu - avatar
5 Respuestas
+ 15
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
27th Jul 2020, 10:23 AM
chaithra Gowda
chaithra Gowda - avatar
+ 3
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😊
27th Jul 2020, 10:20 AM
Aayush $aini
Aayush $aini - avatar
+ 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 ,
27th Jul 2020, 10:23 AM
Abhay
Abhay - avatar
+ 3
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
29th Jul 2020, 6:15 PM
ElectronBoy
ElectronBoy - avatar
0
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
3rd Dec 2020, 2:47 AM
chuck
chuck - avatar