python递归函数辗转相除法
时间: 2023-10-14 07:24:44 浏览: 115
在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递归函数辗转相除法求n,m最大公约数
可以使用递归函数实现辗转相除法求 n 和 m 的最大公约数。辗转相除法也叫欧几里得算法,具体实现如下:
```python
def gcd(n, m):
if m == 0:
return n
else:
return gcd(m, n % m)
```
首先判断如果 m 等于 0,那么最大公约数就是 n,否则继续递归求解,将 m 和 n%m(n 除以 m 的余数)作为参数传入递归函数中。直到 m 等于 0,递归结束,返回 n。
例如,计算 24 和 16 的最大公约数:
```python
print(gcd(24, 16)) # 输出 8
```
这里首先调用 `gcd(24, 16)`,进入函数中,因为 m 不等于 0,所以继续递归调用 `gcd(16, 8)`,因为 24%16 的余数是 8,然后进入 `gcd(16, 8)` 函数中,继续递归调用 `gcd(8, 0)`,因为 16%8 的余数是 0,所以此时 m 等于 0,递归结束,返回 8,即 24 和 16 的最大公约数是 8。
python递归函数辗转相除法求n,m最大公约数并输出
下面是使用递归函数实现辗转相除法求最大公约数的Python代码:
```python
def gcd(n, m):
if m == 0:
return n
else:
return gcd(m, n % m)
n = int(input("请输入第一个数:"))
m = int(input("请输入第二个数:"))
print("{0}和{1}的最大公约数为:{2}".format(n, m, gcd(n, m)))
```
这里定义了一个递归函数`gcd`,接收两个参数n和m,分别表示要求最大公约数的两个数。
如果m等于0,则n就是最大公约数,直接返回n;否则,递归调用`gcd`函数,将m和n%m作为新的参数传入。
最后,通过`format`函数将结果输出。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)