Calculate the extended gcd using a recursive function in Python

Question

I am given the function gcd, which is defined as follows:

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

Now I am asked to write a recursive function gcd2(a,b) that returns a list of three numbers (g, s, t) where g = gcd(a, b) and g = s*a + t*b.

This means that you would enter two values (a and b) into the gcd(a, b) function. The value it returns equals g in the next function.

These same a and b values are then called into gcd2(a, b). The recursive part is then used to find the values for s and t so that g = s*a + t*b.

I am not sure how to approach this because I can't really envision what the "stopping-condition" would be, or what exactly I'd be looping through recursively to actually find s and t. Can anyone help me out?

Why would the stopping case for the three-parameter recursive call be any different than the two-parameter recursive call? — Makoto, Sep 22 '12 at 13:17
This question doesn't really make sense. There will be infinitely many solutions for s and t. — wim, Sep 22 '12 at 13:20
You should probably read the question again, because there is nothing for us to do. Add some more info please! — Hidde, Sep 22 '12 at 13:21
@LoSauer: note that the homework tag is now [officially deprecated](http://meta.stackexchange.com/questions/147100/the-homework-tag-is-now-officially-deprecated); there is no longer a need to tag questions with it. — DSM, Sep 22 '12 at 13:22
@DSM OK. I thought it might help search engines / meta-crawlers... — Lorenz Lo Sauer, Sep 22 '12 at 13:23
I added some more detail that hopefully makes my question more clear. I apologize for the confusion — Jakemmarsh, Sep 22 '12 at 13:28
@wim It does make sense, it doesn't matter which one you have. If you got one pair, you can then calculate all pairs. http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity — Ishtar, Sep 22 '12 at 13:28

senderle · Accepted Answer · 2012-09-22T15:16:57.453

The key insight is that we can work backwards, finding s and t for each a and b in the recursion. So say we have a = 21 and b = 15. We need to work through each iteration, using several values -- a, b, b % a, and c where a = c * b + a % b. First, let's consider each step of the basic GCD algorithm:

21 = 1 * 15 + 6
15 = 2 * 6  + 3
6  = 2 * 3  + 0 -> end recursion

So our gcd (g) is 3. Once we have that, we determine s and t for 6 and 3. To do so, we begin with g, expressing it in terms of (a, b, s, t = 3, 0, 1, -1):

3  = 1 * 3 + -1 * 0

Now we want to eliminate the 0 term. From the last line of the basic algorithm, we know that 0 = 6 - 2 * 3:

3 = 1 * 3 + -1 * (6 - 2 * 3)

Simplifying, we get

3 = 1 * 3 + -1 * 6 + 2 * 3
3 = 3 * 3 + -1 * 6

Now we swap the terms:

3 = -1 * 6 + 3 * 3

So we have s == -1 and t == 3 for a = 6 and b = 3. So given those values of a and b, gcd2 should return (3, -1, 3).

Now we step back up through the recursion, and we want to eliminate the 3 term. From the next-to-last line of the basic algorithm, we know that 3 = 15 - 2 * 6. Simplifying and swapping again (slowly, so that you can see the steps clearly...):

3 = -1 * 6 + 3 * (15 - 2 * 6)
3 = -1 * 6 + 3 * 15 - 6 * 6
3 = -7 * 6 + 3 * 15
3 = 3 * 15 + -7 * 6

So for this level of recursion, we return (3, 3, -7). Now we want to eliminate the 6 term.

3 = 3 * 15 + -7 * (21 - 1 * 15)
3 = 3 * 15 + 7 * 15 - 7 * 21
3 = 10 * 15 - 7 * 21
3 = -7 * 21 + 10 * 15

And voila, we have calculated s and t for 21 and 15.

So schematically, the recursive function will look like this:

def gcd2(a, b):
    if (0 == a % b):
        # calculate s and t
        return b, s, t
    else:
        g, s, t = gcd2(b, a % b)
        # calculate new_s and new_t
        return g, new_s, new_t

Note that for our purposes here, using a slightly different base case simplifies things:

def gcd2(a, b):
    if (0 == b):
        return a, 1, -1
    else:
        g, s, t = gcd2(b, a % b)
        # calculate new_s and new_t
        return g, new_s, new_t

Andy Hayden · Answer 2 · 2012-09-23T13:40:41.157

The base case (stopping condition) is:

if a%b == 0:
    # a = b*k for the integer k=a/b
    # rearranges to b = -1*a + (k+1)*b
    #             ( g =  s*a + t*b )
    return (b, -1, a/b+1) # (g, s, t)

However the exercise is to rewrite the recursive part:

g1, s1, t1 = gcd(b, a%b) # where g1 = s1*b + t1*(a%b)
g, s, t = ???            # where g = s*a + t*b
return (g, s, t)

in terms of g1, s1 and t1... which boils down to rewriting a%b in terms of a and b.

score 0 · Answer 3 · edited May 23 '17 at 10:26

0

"Write a recursive function in Python", at least in CPython, cries for this: be aware of http://docs.python.org/library/sys.html#sys.getrecursionlimit. This is, in my opinion, one of the most important answers to this question. Please do some research on this topic yourself. Also, this thread might be insightful: Python: What is the hard recursion limit for Linux, Mac and Windows?

In conclusion, try to use an iterative instead of a recursive approach in Python whenever possible.

edited May 23 '17 at 10:26

Community

1
1

answered Sep 22 '12 at 14:40

Dr. Jan-Philip Gehrcke

33,287
14
85
130

I would prefer an iterative approach, but unfortunately this is a homework assignment and a recursive method was specified. – Jakemmarsh Sep 22 '12 at 18:24
Recursive is just fine as long as you're bounded, and I think GCD is `O(log(n))` at least. But still good to remember. – o11c Jun 12 '15 at 05:06

score 0 · Answer 4 · answered Sep 20 '17 at 02:27

It is based on Euclidian algorithm using better to while loop continued recursion even better and less execution

def gcd(m,n):
#assume m>= n
if m <n:
    (m,n) = (n,m)
if (m%n) == 0:
    return(n)
else:
    diff =m-n
    #diff >n ?Possible!
    return(gcd(max(n,diff),min(n,diff)))

it can be better by while loop

def gcd(m,n):
if m<n :
    (m,n) =(n,m)
while (m%n) !=0:
    diff =m-n
    (m,n) =(max(n,diff),min(n,diff))
return(n)

Calculate the extended gcd using a recursive function in Python

4 Answers4