python递归函数辗转相除法求n，m最大公约数并输出最大公约数

可以使用递归函数来实现辗转相除法求解最大公约数。具体实现方法如下：

def gcd(n, m):
    if m == 0:
        return n
    else:
        return gcd(m, n % m)

在这个递归函数中，如果 m 等于 0，那么 n 就是最大公约数，因此直接返回 n。否则，就递归调用 gcd 函数，传入 m 和 n % m，继续进行辗转相除的计算。

在主函数中，我们只需要输入要求的两个数 n 和 m，然后调用 gcd 函数即可，最终返回的结果就是它们的最大公约数。代码如下：

n = int(input("请输入第一个数："))
m = int(input("请输入第二个数："))

result = gcd(n, m)

print("最大公约数为：", result)

例如，输入 n = 12，m = 18，输出结果为：

请输入第一个数：12
请输入第二个数：18
最大公约数为： 6

这就是使用递归函数实现辗转相除法求解最大公约数的方法。

相关问题

python递归函数辗转相除法

在Python中实现辗转相除法的递归函数如下：

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

这个函数接受两个整数 a 和 b 作为参数，返回它们的最大公约数。如果 b 为 0，直接返回 a；否则返回 gcd(b, a % b)，其中 % 表示取模运算。这个递归过程会一直进行下去，直到 b 为 0，此时的 a 即为最大公约数。

Python递归辗转相除法求最大公约数

递归辗转相除法是一种求最大公约数的常用方法。它基于以下原理：两个数的最大公约数等于其中较小的数与两数相除余数的最大公约数。下面是使用Python递归辗转相除法求最大公约数的示例代码：

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

# 示例
num1 = 36
num2 = 48
result = gcd(num1, num2)
print("最大公约数为:", result)

在上述代码中，`gcd` 函数接受两个参数 `a` 和 `b`，并使用递归的方式求它们的最大公约数。当 `b` 为 0 时，递归结束，返回 `a` 作为最大公约数。否则，递归调用 `gcd(b, a % b)` 来求 `a` 和 `b` 的余数，并将其作为新的参数传入函数中。

以上代码输出的结果为：

最大公约数为: 12

这样，我们就使用递归辗转相除法成功求得了36和48的最大公约数12。