Python Forum
Trying to understand this GCD recursion
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Trying to understand this GCD recursion
#1
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!!
Reply
#2
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
Reply
#3
(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!! ?
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Can't understand the output of this recursion function bigmit37 5 3,905 Apr-04-2017, 11:15 PM
Last Post: Ofnuts

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020