How to implement a recursive MDC calculation algorithm in Python?

Question

Non-recurring version is below:

def mdc(a,b):
    while b !=0:
        resto = a % b
        a = b
        b = resto

    return a

print(mdc(50,2))

A recursive attempt would be:

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

What do you think? Some other solution?

Answer 1

The non-recursive solution could be rewritten as:

def mdc(a, b):
    while b:
        a, b = b, a % b
    return a

print(mdc(70, 25)) # 5

^{See working on Repl.it | Ideone | Github Gist}

The recursive version could be rewritten as:

def mdc(a, b):
    return a if not b else mdc(b, a % b)

print(mdc(70, 25)) # 5

^{See working on Repl.it | Ideone | Github Gist}

But the simplest solution is the native function:

from fractions import gcd

print(gcd(70, 25)) # 5

^{See working on Repl.it | Ideone | Github Gist}

Answer 2

Hello, everything seems to be right around here.
Only a little information is that in python instead of:

a = b
b = resto

One could write:

a,b = b,resto

And I personally prefer to use the recursive version because I find it easier to debug.
And I don’t think there’s any other simple way, like the ones presented, to implement this algorithm.

Answer 3

I built this code for this situation, it is possible to pass a list of numbers to facilitate when actually using the function.

def __mdc_(x,y):
    while(y):
        x,y=y,x%y
    return x

def mdc(nums):

    if len(nums) == 2:
        return __mdc_(nums[0], nums[1])
    else:
        mdc_val = __mdc_(nums[0], nums[1])
        nums[0] = mdc_val
        del nums[1]
        return mdc(nums)

>>> mdc([30, 54, 72])
>>> 6

Answer 4

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