递归法求最大公约数和最小公倍数的实现代码

递归法求最大公约数和最小公倍数的实现代码，可以分为以下两个步骤：

1.实现求最大公约数的递归函数

我们可以使用辗转相除法（又称欧几里得算法）来求解最大公约数，其核心代码如下：

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

该函数的原理是，若a和b的最大公约数为c，则有以下结论：a = m * c，b = n * c，其中m、n均为正整数。利用辗转相除法，设r = a % b，则有：

a = b * (a // b) + r

因此，a和b的最大公约数等于b和r的最大公约数。我们可以一直递归执行gcd(b, a % b)，直到b为0时，a即为最大公约数。

2.实现求最小公倍数的递归函数

最小公倍数等于两个数的乘积除以它们的最大公约数，其代码如下：

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

首先利用前面编写的gcd函数求出a和b的最大公约数，然后将它们相乘，再除以最大公约数，即可得到最小公倍数。这里需要注意的是，为了避免a和b太大导致溢出，需要在计算乘积时先除以最大公约数。

示例说明

我们来看几个具体的例子，以更好地理解递归法求最大公约数和最小公倍数的实现代码：

示例一

假设我们要求解数字24和16的最大公约数和最小公倍数，那么我们可以这样进行调用：

print(gcd(24, 16)) # 输出 8
print(lcm(24, 16)) # 输出 48

此时gcd函数将递归调用一次，得到16和8的最大公约数，最终返回值为8；然后lcm函数将调用gcd函数一次，再相乘再除以最大公约数，得到最小公倍数48，最终返回值也为48。

示例二

假设我们要求解数字36和132的最大公约数和最小公倍数，那么我们可以这样进行调用：

print(gcd(36, 132)) # 输出 12
print(lcm(36, 132)) # 输出 396

此时gcd函数将递归调用一次，得到108和36的最大公约数，继续递归调用，得到36和0的最大公约数，最终返回值为36；然后lcm函数将调用gcd函数一次，再相乘再除以最大公约数，得到最小公倍数396，最终返回值也为396。