用递归算法求两个整数的最小公倍数

以下是Python代码实现：

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

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

其中，gcd函数用于求两个整数的最大公约数，lcm函数用于求两个整数的最小公倍数。递归的思想在gcd函数中体现，当b为0时，a就是最大公约数，否则继续递归，将b和a%b作为参数传入函数中。最小公倍数可以通过公式a*b/gcd(a,b)来计算，其中//表示整除，保证结果为整数。

相关问题

用java递归算法求两个整数的最小公倍数

以下是用 Java 递归算法求两个整数的最小公倍数的示例代码：

public class LCM {
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
    
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
    
    public static void main(String[] args) {
        int a = 12;
        int b = 18;
        int lcm = lcm(a, b);
        System.out.println("The LCM of " + a + " and " + b + " is " + lcm);
    }
}

在上面的代码中，我们定义了两个方法 `lcm` 和 `gcd` 来计算两个整数的最小公倍数和最大公约数。`lcm` 方法首先计算两个整数的乘积，然后除以它们的最大公约数来得到最小公倍数。`gcd` 方法使用递归算法来计算两个整数的最大公约数。该方法的基本思想是，如果两个整数 a 和 b 的最大公约数是 c，则 a 和 b 可以表示为 c 的倍数和余数的和，即 a = c * x + r1，b = c * y + r2，其中 r1 和 r2 分别是 a 和 b 对 c 取模的余数。由于 c 是 a 和 b 的公约数，所以它也是 r1 和 r2 的公约数。因此，我们可以递归地计算 r1 和 r2 的最大公约数，直到 r2 等于 0 为止，此时 c 就是 a 和 b 的最大公约数。

设计递归算法，计算两个非负整数的最小公倍数

设计递归算法计算两个非负整数的最小公倍数（LCM），可以利用一个基本的数学原理：两个数a和b的最小公倍数等于它们的最大公约数（GCD）乘以较大的那个数。而两个数的最大公约数可以用欧几里得算法来计算。

以下是递归算法的基本思路：

1. 定义基本情况：如果其中一个数为0，那么另一个数就是最小公倍数；如果两个数相等，那么它们本身就是最小公倍数。
2. 递归情况：如果a和b都不为0，并且a > b，那么最小公倍数 = a * GCD(b, a % b)。
- 计算a除以b的余数（即a % b）
- 调用自身函数，传入较小的数b和余数(a % b)，因为GCD(b, a % b)就等于b和a除以b后的余数的GCD。

下面是伪代码形式：

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

def lcm(a, b):
    if a == 0 or b == 0:
        return 0
    else:
        return a // gcd(a, b) * b  # 或者直接写成 return a * b // gcd(a, b)