设计一个python算法:设计递归函数,求两个数的最大公约数。 思路:首先判断m能否整除n,能则最大公约数为n;如不能则采用辗转相除法,用较大数除以较小数,再用出现的余数(第一余数)去除除数,再用出现的余数(第二余数)去除第一余数,如此反复,直到最后余数是0为止。如果是求两个数的最大公约数,那么最后的除数就是这两个数的最大公约数。
时间: 2024-03-27 22:36:37 浏览: 68
用递归算法实现两个整数最大公约数的计算
3星 · 编辑精心推荐
好的,以下是递归函数求两个数的最大公约数的Python算法:
```
def gcd(m, n):
if m % n == 0:
return n
else:
return gcd(n, m % n)
```
其中,`m`和`n`为两个正整数,函数使用了辗转相除法来求最大公约数。当`m`能够整除`n`时,`n`即为最大公约数;否则,递归调用`gcd`函数,以`n`和`m % n`作为新的参数继续执行计算,直到`m % n`为0,此时`n`即为最大公约数。
阅读全文