[SOLVED]How to understand recursion

Question

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

Answer 1

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

Answer 2

https://www.sololearn.com/discuss/307407/?ref=app

Answer 3

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

Answer 4

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

Answer 5

To understand recursion one must first understand recursion.

Answer 6

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

Answer 7

Watch Inception movie😂😂
Dreams inside Dreams.✌😎

Answer 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

Answer 9

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

Answer 10

@Hatsy Rey thank you for the explanation I know now where I went wrong it is the operator precedence. this clears the uncertainity thanks

Answer 11

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.

Answer 12

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.

Answer 13

infinite loop with condition

Answer 14

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

Answer 15

great

Answer 16

excelent explanation. congratulations.

Answer 17

Are these Fibonacci numbers? Should it not be return (fb(n-1) + fb(n-2)) ?

Answer 18

To understand what recursion is, you need to understand what recursion is... :)) Old Programming Pun

Answer 19

Remember: Recursion is the repeated application of a recursive procedure or definition!

Answer 20

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