如何在Python中使用递归函数找到最大公约数？

Question

我被要求使用 Python 中的递归函数找到整数x和y的最大公约数。条件表示：如果 y 等于 0，则 gcd (x,y) 为x；否则 gcd(x,y) 为 gcd(y,x%y)。为了尝试该代码，我被要求从用户那里获取两个整数。这是我尝试过的：

def gcd(x , y):
    if y == 0:
        return x
    else:
        return (y, x % y)

num_one = int(input('Enter a value for x: '))
num_two = int(input('Enter a value for y: '))
if num_two == 0:
    print(num_one)
else:
    print(gcd(num_two))

这是我得到的错误： TypeError: gcd() Missing 1 requiredpositional argument: 'y'

先感谢您。

Answer 1

试试这个，简单的改变：

def gcd(x , y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

与 math.gcd 相比：

In [1231]: gcd(127,127**2)                                                                                                                                                                                 
Out[1231]: 127

In [1232]: math.gcd(127, 127**2)                                                                                                                                                                           
Out[1232]: 127

并改变这个：

    print(gcd(num_two))

到

    print(gcd(num_one, num_two))

完整变更：

def gcd(x , y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

num_one = int(input('Enter a value for x: '))
num_two = int(input('Enter a value for y: '))
if num_two == 0:
    print(num_one)
else:
    print(gcd(num_one, num_two))

输出：

Enter a value for x: 46
Enter a value for y: 12
2