Trying to understand this GCD recursion

Trying to understand this GCD recursion - Printable Version

+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Trying to understand this GCD recursion (/thread-20903.html)

Trying to understand this GCD recursion - ThomasAquinas - Sep-05-2019

def euclidean(a, b):
    if b==0: return a
    return euclidean(b, a%b)

It works to give these results:

print(euclidean(8, 6))# 2

print(euclidean(25, 5))# 5

print(euclidean(49, 14))# 7

I am trying to understand recursion, but I can't understand the return (3rd line) here, and how it makes this function work. I would really appreciate a breakdown so I can follow what's going on at each step. Thank you for any help you can provide!!

RE: Trying to understand this GCD recursion - ibreeden - Sep-05-2019

Yes, Fascinating isn´t it?
I tried to make a schema of it. Does it make that clearer?

Output:euclidean(8, 6)
    #Recurse 0
    if b==0:  #False for b==6
    return euclidian(6, 8%6 := 2)
    .   #Recurse 1
    .   if b==0: #False for b==2
    .   return euclidean(2, 6%2 := 0)
    .   .   #Recurse 2
    .   .   if b==0: #True at last; so return 2
    .   return 2
    return 2

RE: Trying to understand this GCD recursion - ThomasAquinas - Sep-05-2019

(Sep-05-2019, 06:08 PM)ibreeden Wrote: Yes, Fascinating isn´t it?
I tried to make a schema of it. Does it make that clearer?

Output:euclidean(8, 6)
    #Recurse 0
    if b==0:  #False for b==6
    return euclidian(6, 8%6 := 2)
    .   #Recurse 1
    .   if b==0: #False for b==2
    .   return euclidean(2, 6%2 := 0)
    .   .   #Recurse 2
    .   .   if b==0: #True at last; so return 2
    .   return 2
    return 2

That is great! I can tell this will take many practice exercises to feel intuitive, but seeing the steps laid out like that is exactly what I was hoping for to clarify it. Thank you so much!! ?