Recursion Python | Sololearn: Learn to code for FREE!


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

7/27/2020 10:01:04 AM


5 Answers

New Answer


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


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😊


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 ,


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


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