递归实现求最大公约数C语言

在C语言中，可以使用递归来实现欧几里得算法，也就是辗转相除法来求两个整数的最大公约数（Greatest Common Divisor，GCD）。递归版本的欧几里得算法如下：

#include <stdio.h>

// 递归函数计算最大公约数
int gcd(int a, int b) {
    // 基本情况：当b为0时，a就是最大公约数
    if (b == 0)
        return a;
    
    // 递归情况：继续将较小的数b作为新的a，较大的数a除以b得到的余数作为新的b
    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；否则继续迭代，直到找到最大公约数。

相关问题

递归函数求最大公约数c语言

递归函数是一种在函数内部调用自身的编程技巧，常用于解决需要分治或自相似的问题，比如计算最大公约数（GCD）。在C语言中，我们可以利用欧几里得算法（也称辗转相除法）来编写一个递归版本的求最大公约数函数。下面是一个简单的例子：

#include <stdio.h>

// 递归函数，计算两个数的最大公约数
int gcd(int a, int b) {
    // 基线条件：如果b为0，则a就是GCD
    if (b == 0)
        return a;
    
    // 递归调用，将较小的数作为新的a，较大的数作为新的b
    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`函数会一直调用自身，直到第二个参数为0为止，这时返回第一个非零参数即为最大公约数。递归结束的条件至关重要，它保证了函数不会无限循环。

递归法求最大公约数pta用c语言实现

递归法求最大公约数（Greatest Common Divisor, GCD）通常使用欧几里得算法（Euclidean Algorithm）。在C语言中，你可以通过下面这个简单的递归函数来实现：

#include <stdio.h>

// 定义递归函数计算GCD
int gcd(int a, int b) {
    // 基本情况：如果b为0，那么a就是GCD
    if (b == 0)
        return a;
    
    // 递归调用gcd函数，交换a和b的位置
    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`函数会不断调用自身，每次都将第二个数替换为两数相除的余数，直到余数为0，此时第一个数即为最大公约数。