Why does “return n” run 5 times, resulting 10110 ???? (Python recursion)

Question

def rec(n):
n %= 5
if n <= 1:
print(n)
return n
else:
return rec(n - 1) + rec(n - 2)
print(rec(9))

Answer 1

Lets look:
9 % 5 = 4
if don't work, go to else
Rec(4-1) + rec (4-2)
And going again in cycle. Until n<=1.

Answer 2

Here is a hand-drawn diagram made by me as explanation for this kind of double recursion, if anyone finds it useful:

https://drive.google.com/file/d/1XkYU0M9c5PtBwDSdgDJiDqjtz8V0rS82/view?usp=drivesdk

It also shows the execution order that I missed earlier.

Answer 3

Wait 30 minuts, i'll try to explain)

Answer 4

First n=9:
n%5 =4
Got rec(4-1) and (4-2)
Second n=3:
3 % 5 = 3
Got rec (3-1) and (3-2)
Third n = 2:
2 % 5 = 2
Got rec (2-1) and (2-2)
Four n=1:
Write 1
Five go back to n = 2-2 =0:
Write 0
And go round until end...
Every time you recal "rec" it's must return value.

Answer 5

You calling function in function. First rec (9) going to call another two rec's rec(3) and rec (2). Rec (3) calling another two rec's, rec (2) and rec (1), and after calling rec (2) from prev. And every of it return you a value.

Answer 6

Yes, but because of calling print (n) inside rec() when it recive on each level n<=1 you got printing result multiple times. And after all printing final return.

Answer 7

desktop: PyCharm
mobil: Pythonista

Answer 8

Thanks, Jevgenij! That explains the following for me:

rec(n-1) —> returns 1,0
rec(n-2) —> returns 0

but how does it return 5 times?

Answer 9

And another thing, you call "print" inside "print".

Answer 10

So after the first iteration:

rec(n-1) —> returns 1,0
rec(n-2) —> returns 0

how does it continue?

Answer 11

...until each branches return to the original line which called the recursion

Answer 12

yes, you’re right, multiple print was just for debugging purpose

Answer 13

What IDE do you using?

Answer 14

and you?

Answer 15

...and the snippet was in a SoloLearn challenge which I have lost (obviously:)

Answer 16

Try Visual Studio Code ( https://code.visualstudio.com/ )
It's will give you posibility to debug each line step-by-step

Answer 17

Yes, I love VSC (and using it also). The UI is very nice and modern, and there are a tons of plugins.

Answer 18

When you calling debuger whis breakpoints you can control every state of variables on every step. Try it in VSC)))