编写程序辗转相除法求最大公约数的递归函数
时间: 2023-09-01 13:08:37 浏览: 50
好的,以下是用递归实现辗转相除法求最大公约数的 Python 代码:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
# 测试
print(gcd(12, 18)) # 输出6
print(gcd(25, 15)) # 输出5
```
这个函数的实现非常简单。如果 b 等于 0,那么 a 就是最大公约数。否则,我们需要用 a 除以 b 的余数来递归调用这个函数,直到 b 等于 0 为止。这个函数的时间复杂度是 O(log n),其中 n 是 a 和 b 的最大值。
相关问题
Python编编写辗转相除法求最大公约数的递归函数。
可以使用Python编写辗转相除法求最大公约数的递归函数,代码如下:
```
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
其中,a和b分别是两个需要求最大公约数的整数。函数使用递归方式实现辗转相除法,当b为0时,a即为最大公约数。否则,将b和a%b作为参数递归调用函数gcd。
python编写辗转相除法求最大公约数的递归函数
下面是使用 Python 编写辗转相除法求最大公约数的递归函数:
```python
def gcd(a, b):
if b == 0:
return a
else:
return gcd(b, a % b)
```
其中,如果 b 等于 0,那么 a 就是最大公约数;否则,递归调用 gcd 函数,将 b 和 a 对 b 取模的结果作为参数传入。每次递归都会使得 b 变成更小的数,直到找到最大公约数。