+ 47

[SOLVED]How to understand recursion

there is this code that made me uncertain of recursion. at first I tried having a recursion of one. but as I add the same line of code it became uncertain as to why it outputed 16 instead of 8 when i called fb(5) but in fb(3) its output is 4. Can someone explain why it turned this way?? I would very much like to understand the logic behind it. Anyways, thanks in advance https://code.sololearn.com/c0SgITB23S0s/?ref=app

21st May 2018, 2:54 AM
Neet
Neet - avatar
32 Answers
+ 85
This is your program: def fb(n): if n == 0: return 0 elif n == 1: return 1 else: return (fb(n-1) +fb(n-1)) print(fb(5)) Always try handtracing your program. fb(5) fb(4)+fb(4) fb(3)+fb(3)+fb(3)+fb(3) fb(2)+fb(2)+fb(2)+fb(2)+fb(2)+fb(2)+fb(2)+fb(2) fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1)+fb(1) 16
21st May 2018, 3:06 AM
Hatsy Rei
Hatsy Rei - avatar
26th May 2018, 6:08 PM
Jaydeep Khatri
Jaydeep Khatri - avatar
+ 11
You should draw a flow chart of the invocations of the function. For factorial recursion, ldt the function be f. f(5) triggers 5*f(4), f(4) triggers 4*f(3), . . . f(1) triggers 1*f(0). Now defined f(0)=1, Hence, f(1)=1*1=1 f(2)=2*1=2 f(3)=3*2=6 . . f(5)=5*24=120 Thks is how it works
26th May 2018, 4:13 PM
👑 Prometheus 🇸🇬
👑 Prometheus 🇸🇬 - avatar
+ 10
think u are upstairs at home.and u have a ball in hand the ball slipped from and I it reached the ground floor now to get the ball your should reach the ground and take the ball and climb the stairs again now you got the ball and reached ur old position this is the same way how a recursive function works. now think of a recursive function as a stair. to find the value it goes down to bottom.after finding it it reclimbs the stair stepper by step returning the result and reach the top again
26th May 2018, 3:48 PM
Abhiram ARS
Abhiram ARS - avatar
+ 10
To understand recursion one must first understand recursion.
27th May 2018, 7:51 AM
Paul Grasser
Paul Grasser - avatar
+ 9
Recursive Acronyms are very popular in computing. GNU - GNU is Not Unix LAME -Lame is Not an MP3 Encoder one for the Pythonistas PIP -Pip Installs Programs https://en.m.wikipedia.org/wiki/Recursive_acronym
26th May 2018, 4:15 PM
Mike Choy
Mike Choy - avatar
+ 9
Watch Inception movie😂😂 Dreams inside Dreams.✌😎
27th May 2018, 2:28 PM
Junth Basnet
+ 8
I think the program did not give required results not because you don't understand recursion, but you wrote incorrect program. the Fibonacci sequence is defined by return (fb(n-1) + fb(n-2)) not return (fb(n-1) + fb(n-1)) iff n>1. A quick explanation to recursion: calling a function inside the itself is recursion, what I understand. Since it calls itself, the program must specify a break point, if not the function will run endlessly, in this case it's the : if n==0 elif n==1
26th May 2018, 3:20 PM
scientist
scientist - avatar
+ 7
---------5 4 4 3 3 3 3 2 2 2 2 2 2 2 2 11 11 11 11 11 11 11 11 this is a recursion tree fb (5) is calling twice fb (4) and fb(4) is further calling twice fb (3) and so on until fb (1) is called which retuns 1. sum of child nodes is returned to parent nodes. you can count 16 leaf nodes which indicates sum of these 16 nodes is ultimately returned to their parent nodes . This is called a recursion tree. Unsolicited advise: if you understood so far, you can see fb (3) is called again and again although it is going to give same output no matter what. What if we store fb (3) in an array and we could prevent calling fb (3) which would save a lot of steps. in that way fb (4),fb (3),fb (2),fb (1) will be called only once and value of it can be used again and again when needed. This is called memoization. And this algorithm design is called Dynamic programming.
26th May 2018, 5:16 PM
Viraj Singh
Viraj Singh - avatar
+ 5
@Hatsy Rey thank you for the explanation I know now where I went wrong it is the operator precedence. this clears the uncertainity thanks
21st May 2018, 3:11 AM
Neet
Neet - avatar
+ 5
You have 2 base cases (n=0 and n=1) for a good reason: you are going to use 2 previous numbers to obtain a current number. You will use fb(n-1) and fb(n-2) to get fb(n). If you would have needed only fb(n-1), then one base case n=0 would suffice.
26th May 2018, 4:13 PM
ksvlna5
+ 5
you wrote: return (fb(n-1)+fb(n-1)) It separates the number to 2 ways. You entered 5, so the function returns fb(4) twice. And it continues separating, so you got 2⁴=16. 2 because you separated it to 2 ways (in the return). 4 because it's the difference between 5 and 1 (the exit condition). You should write: return (n + fb(n-1)) It will keep only one way.
26th May 2018, 8:25 PM
‎Dael Winograd
‎Dael Winograd - avatar
+ 5
infinite loop with condition
26th May 2018, 9:26 PM
Vlastimir Bulatovic
Vlastimir Bulatovic - avatar
+ 5
I had a lot of problems with understanding recursion too. Our Math teacher told us to solve a math function (e.g. f(x) = 2^x) with recursion. To solve a math function with recursion you have to imagine a graph of the function and look how the y values change when you go one step in x direction. I think we need an example: function normal: f(x) = 2 * x graph: line, wich increases 2 y values per one x value. So if you go one step in x direction the graph increases 2 y values. function recursion: f(x) = f(x - 1) + 2 example 2: function normal: f(x) = 2 ^ x graph: one step in x direction => y value is the double of the old value function recursion: f(x) = f(x - 1) * 2 It's easy to understand recursion if you imagine you function as a math function, wich takes the old value (x-1) +,-,×,÷ something. P.S. don't forget to define a basecase
27th May 2018, 8:45 AM
Tim
Tim - avatar
+ 4
great
21st May 2018, 5:59 AM
lan7
+ 4
excelent explanation. congratulations.
24th May 2018, 4:45 AM
Enrique
Enrique - avatar
+ 4
Are these Fibonacci numbers? Should it not be return (fb(n-1) + fb(n-2)) ?
26th May 2018, 3:21 PM
ksvlna5
+ 4
To understand what recursion is, you need to understand what recursion is... :)) Old Programming Pun
30th May 2018, 6:59 PM
Gami
Gami - avatar
+ 3
Remember: Recursion is the repeated application of a recursive procedure or definition!
26th May 2018, 5:15 PM
Siddharth
Siddharth - avatar
+ 3
as hatsy rei said it's always a good idea to simulate your program in a peace of paper manually that way you understand the flow of your program and learn more from your mistakes by the way if you are trying to calculate the Fibonacci sequence to a given integer then you should change it to : return fb(n-1) + fb(n-2) cause every term is the sum of the last two preceding terms , otherwise nevermind. ;)
26th May 2018, 11:53 PM
MedG
MedG - avatar