Python递归实现最大公约数与最小公倍数问题

最大公约数（Greatest Common Divisor，简称GCD）问题是计算两个或多个整数的最大公约数，最小公倍数（Least Common Multiple，简称LCM）是计算两个或多个整数的最小公倍数。

Python可以使用递归来实现这两个问题。具体实现方法如下：

1. 实现最大公约数（GCD）

使用辗转相除法可求得最大公约数。具体流程如下：

• 如果a%b==0，则b就是a和b的最大公约数
• 如果a%b!=0，则a和b的最大公约数等于b和a%b的最大公约数

利用递归可以简单地实现该算法，代码如下：

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

2. 实现最小公倍数（LCM）

最小公倍数可以通过求最大公约数解决，具体实现方法如下：

• 首先求出a和b的最大公约数gcd
• 然后，最小公倍数lcm等于a*b/gcd

利用递归可以实现该算法，代码如下：

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

def lcm(a, b):
    return a * b / gcd(a, b)

示例代码：

print(gcd(24, 60)) # 12
print(lcm(24, 60)) # 120
print(gcd(12, 8)) # 4
print(lcm(12, 8)) # 24

输出结果：

12
120
4
24