c语言 最大公约数 递归

在C语言中，计算两个整数的最大公约数（Greatest Common Divisor, GCD）可以通过递归算法来实现。递归是一种解决问题的方法，其中函数调用自身直到达到基本情况为止。下面是使用欧几里得算法（Euclidean Algorithm）求最大公约数的递归版本：

#include <stdio.h>

// 递归函数，计算两个数的最大公约数
int gcd(int a, int b) {
    // 基本情况：如果b为0，则a即为最大公约数
    if (b == 0) 
        return a;
    
    // 否则，将较小数作为新的a，较大数除以较小数得到的余数作为新的b
    else
        return gcd(b, a % b);
}

int main() {
    int num1, num2;
    printf("请输入两个整数：");
    scanf("%d %d", &num1, &num2);

    int result = gcd(num1, num2);
    printf("两数的最大公约数是：%d\n", result);

    return 0;
}

相关问题

c语言求最大公约数递归

你可以使用递归的方法来求解两个数的最大公约数。下面是使用递归实现求最大公约数的C语言代码示例：

#include <stdio.h>

// 递归函数，用于求最大公约数
int gcd(int a, int b) {
    if (b == 0) {
        return a;    } else {
        return gcd(b, a % b);
    }
}

int main() {
    int num1, num2;
    printf("请输入两个整数：");
    scanf("%d %d", &num1, &num2);
    
    int result = gcd(num1, num2);
    
    printf("最大公约数为：%d\n", result);
    
    return 0;
}

在这个代码示例中，`gcd()` 函数用于递归地求解最大公约数。如果第二个数 `b` 等于0，那么最大公约数就是第一个数 `a`。否则，递归调用 `gcd()` 函数，并将第二个参数设为 `a` 除以 `b` 的余数。通过不断缩小问题规模，直到找到最大公约数。

在 `main()` 函数中，首先要求用户输入两个整数，并将它们传递给 `gcd()` 函数进行计算。最后，将计算得到的最大公约数输出到控制台上。

希望这个代码示例对你有所帮助！如果你有任何问题，请随时提问。

c语言最小公倍数递归

最小公倍数的C语言递归实现如下：

int gcd(int a, int b);
int lcm(int a, int b);

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int gcd(int a, int b) {
    return a % b ? gcd(b, a % b) : b;
}

上述代码中，`gcd`函数使用递归实现了求两个整数的最大公约数，`lcm`函数则使用了公式法计算最小公倍数。在`lcm`函数中调用了`gcd`函数来求最大公约数。