如何在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 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

Answer 2

递归函数调用自己。您没有从 gcd 中调用 gcd，因此您没有遵循作业的指示。

你 return 0 作为基本条件，这样你就不会得到 Whosebug :)

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

请阅读这个例子。

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

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

How to find greatest common divisor using recursive function in Python?

python

recursion

controls

input

function