# Recursion oddity

I've been having a problem with a recursive factorization algorithm I've been writing in Sage code. The problem is reproduced on my machine using the code below:

def gcd_recur(num):
if(num <= 1):
return
g = gcd(15,num)
print "GCD of 15 and {0}: {1}".format(num, g)
gcd_recur(num/2)

gcd_recur(50)


The result I'm getting is:

GCD of 15 and 50: 5
GCD of 15 and 25: 1
GCD of 15 and 25/2: 1
GCD of 15 and 25/4: 1
GCD of 15 and 25/8: 1
GCD of 15 and 25/16: 1


However, I can run the code below outside of the algorithm and receive the correct result:

gcd(15, 25)

5


Are there some variable scoping issues that I'm not seeing here? Thanks.

edit retag close merge delete

Can you be more clear as to what the answer that you want to get from gcd_recur? The code you posted is working correctly as it is written.

( 2011-11-12 17:00:02 -0500 )edit

Sort by ยป oldest newest most voted

You're probably running an older version of Sage. For reasons I (famously) disagreed with, it used to be the case that gcd(2, 4/2) and your gcd(15,50/2) would return 1, because the second term is a rational, and the gcd of rationals was defined to be 1. I thought this was very silly, even though defensible.

After a long discussion on sage-devel (following my first ever post there!) and thanks to work by Simon King (trac # 10771), this is no longer the case, and your code seems to work:

sage: gcd_recur(50)
GCD of 15 and 50: 5
GCD of 15 and 25: 5
GCD of 15 and 25/2: 5/2
GCD of 15 and 25/4: 5/4
GCD of 15 and 25/8: 5/8
GCD of 15 and 25/16: 5/16

more

Thanks, I am a version behind. I've also found that gcd(15, ceil(50/2)) works for what I'm doing.

( 2011-11-12 23:26:20 -0500 )edit