如何在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（）缺少1个必需的位置参数：'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))

to

    print(gcd(num_one, num_two))

Answer 2

递归函数自称。您不是从gcd内部呼叫gcd，所以您没有遵循作业的指示。

您返回0作为基本条件，这样就不会以stackoverflow结束：)

然后，您从包含方法中调用方法本身。在您的情况下，您只是在左括号之前的第5行缺少了gcd。

请阅读本示例，但实际上要调整您的代码。

https://www.freecodecamp.org/news/recursion-is-not-hard-858a48830d83/