使用递归求解最大公约数

介绍

在数学中，两个数的最大公约数（GCD, Greatest Common Divisor）通常定义为能够整除这两个数且不留余数的最大正整数。在本实验中，我们将学习如何编写一个使用递归来求解两个数 GCD 的 C 语言程序。

注意：你需要自己创建文件 ~/project/main.c 来练习编程，并学习如何使用 gcc 编译和运行它。

cd ~/project
## 创建 main.c
touch main.c
## 编译 main.c
gcc main.c -o main
## 运行 main
./main

读取输入数字

首先，我们需要从用户那里获取两个整数输入，以便计算它们的 GCD。我们将使用 scanf() 函数来读取输入。

#include<stdio.h>

int main()
{
    int a, b;
    printf("输入两个数字以计算它们的 GCD: \n");
    scanf("%d%d", &a, &b);
    // 其余代码
    return 0;
}

定义递归函数以计算 GCD

我们将使用一个递归函数来计算两个输入数字的 GCD。该递归函数将包含两个整数参数。函数将持续调用自身，直到两个数字的值相同，并返回该值作为 GCD。

int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

从主函数调用递归函数

在这一步中，递归函数将以两个输入数字（a 和 b）作为参数被调用。递归函数的返回值将被存储在一个整数变量（gcd）中。

int gcd = find_gcd(a, b);
printf("GCD of %d and %d is: %d\n", a, b, gcd);

完整示例代码

#include <stdio.h>

// 声明递归函数
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("输入两个数字以计算它们的 GCD: \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("GCD of %d and %d is: %d\n", a, b, gcd);
    return 0;
}

// 定义函数
int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

总结

在本实验中，我们学习了如何编写一个使用递归来计算两个数 GCD 的 C 语言程序。我们利用递归函数通过不断调用自身并修改输入参数来计算 GCD，直到达到基准条件。该程序可用于解决需要计算两个数 GCD 的数学问题。