ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sat, 12 Nov 2011 23:26:20 -0600Recursion oddityhttp://ask.sagemath.org/question/8468/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.
Sat, 12 Nov 2011 15:04:37 -0600http://ask.sagemath.org/question/8468/recursion-oddity/Comment by Mike Hansen for <p>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:</p>
<pre><code>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)
</code></pre>
<p>The result I'm getting is:</p>
<pre><code>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
</code></pre>
<p>However, I can run the code below outside of the algorithm and receive the correct result:</p>
<pre><code>gcd(15, 25)
5
</code></pre>
<p>Are there some variable scoping issues that I'm not seeing here? Thanks.</p>
http://ask.sagemath.org/question/8468/recursion-oddity/?comment=20915#post-id-20915Can 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.Sat, 12 Nov 2011 17:00:02 -0600http://ask.sagemath.org/question/8468/recursion-oddity/?comment=20915#post-id-20915Answer by DSM for <p>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:</p>
<pre><code>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)
</code></pre>
<p>The result I'm getting is:</p>
<pre><code>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
</code></pre>
<p>However, I can run the code below outside of the algorithm and receive the correct result:</p>
<pre><code>gcd(15, 25)
5
</code></pre>
<p>Are there some variable scoping issues that I'm not seeing here? Thanks.</p>
http://ask.sagemath.org/question/8468/recursion-oddity/?answer=12894#post-id-12894You'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)](http://trac.sagemath.org/sage_trac/ticket/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
Sat, 12 Nov 2011 17:07:08 -0600http://ask.sagemath.org/question/8468/recursion-oddity/?answer=12894#post-id-12894Comment by Birdman for <p>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.</p>
<p>After a long discussion on sage-devel (following my first ever post there!) and thanks to work by Simon King <a href="http://trac.sagemath.org/sage_trac/ticket/10771">(trac # 10771)</a>, this is no longer the case, and your code seems to work:</p>
<pre><code>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
</code></pre>
http://ask.sagemath.org/question/8468/recursion-oddity/?comment=20914#post-id-20914Thanks, I am a version behind. I've also found that gcd(15, ceil(50/2)) works for what I'm doing.Sat, 12 Nov 2011 23:26:20 -0600http://ask.sagemath.org/question/8468/recursion-oddity/?comment=20914#post-id-20914