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

Question

我被要求找到整数的最大公约数 x 和 y 在 Python 中使用递归函数。条件表示:如果 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 required positional 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