+ 1

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

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

31st Dec 2019, 11:32 AM
Prof. Dr. Zoltán Vass
18 odpowiedzi
+ 2
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.
31st Dec 2019, 12:26 PM
Євгеній Дерікот
Євгеній Дерікот - avatar
+ 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.
3rd Jan 2020, 7:04 AM
Prof. Dr. Zoltán Vass
+ 1
Wait 30 minuts, i'll try to explain)
31st Dec 2019, 12:57 PM
Євгеній Дерікот
Євгеній Дерікот - avatar
+ 1
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.
31st Dec 2019, 1:34 PM
Євгеній Дерікот
Євгеній Дерікот - avatar
+ 1
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.
2nd Jan 2020, 8:50 PM
Євгеній Дерікот
Євгеній Дерікот - avatar
+ 1
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.
2nd Jan 2020, 8:55 PM
Євгеній Дерікот
Євгеній Дерікот - avatar
+ 1
desktop: PyCharm mobil: Pythonista
2nd Jan 2020, 8:58 PM
Prof. Dr. Zoltán Vass
0
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?
31st Dec 2019, 12:35 PM
Prof. Dr. Zoltán Vass
0
And another thing, you call "print" inside "print".
31st Dec 2019, 1:36 PM
Євгеній Дерікот
Євгеній Дерікот - avatar
0
So after the first iteration: rec(n-1) —> returns 1,0 rec(n-2) —> returns 0 how does it continue?
2nd Jan 2020, 8:36 PM
Prof. Dr. Zoltán Vass
0
...until each branches return to the original line which called the recursion
2nd Jan 2020, 8:52 PM
Prof. Dr. Zoltán Vass
0
yes, you’re right, multiple print was just for debugging purpose
2nd Jan 2020, 8:57 PM
Prof. Dr. Zoltán Vass
0
What IDE do you using?
2nd Jan 2020, 8:58 PM
Євгеній Дерікот
Євгеній Дерікот - avatar
0
and you?
2nd Jan 2020, 8:59 PM
Prof. Dr. Zoltán Vass
0
...and the snippet was in a SoloLearn challenge which I have lost (obviously:)
2nd Jan 2020, 9:01 PM
Prof. Dr. Zoltán Vass
0
Try Visual Studio Code ( https://code.visualstudio.com/ ) It's will give you posibility to debug each line step-by-step
2nd Jan 2020, 9:02 PM
Євгеній Дерікот
Євгеній Дерікот - avatar
0
Yes, I love VSC (and using it also). The UI is very nice and modern, and there are a tons of plugins.
2nd Jan 2020, 9:05 PM
Prof. Dr. Zoltán Vass
0
When you calling debuger whis breakpoints you can control every state of variables on every step. Try it in VSC)))
2nd Jan 2020, 9:07 PM
Євгеній Дерікот
Євгеній Дерікот - avatar