谁能解释这个递归函数我不明白它如何返回任何东西？

Question

我不明白这个递归函数是如何计算gcd的，有人能详细解释一下这个递归函数如何返回gcd吗？

#include <stdio.h>

long gcd(long, long);

int main() {
    long x, y, hcf, lcm;

    printf("Enter two integers\n");
    scanf("%ld%ld", &x, &y);

    hcf = gcd(x, y);
    lcm = (x*y)/hcf;

    printf("Greatest common divisor of %ld and %ld = %ld\n", x, y, hcf);
    printf("Least common multiple of %ld and %ld = %ld\n", x, y, lcm);

    return 0;
}

long gcd(long a, long b) {
    if (b == 0) {
        return a;
    }
    else {
        return gcd(b, a % b);
    }
}

Answer 1

您可以在这里阅读有关此算法的信息:Euclidean algorithm

基本上，如果

a == bq + r

何时 r是除法的余数 a通过b (所以0 <= r < b)

然后

gcd(a, b) == gcd(b, r)

请注意a%b余数是 r 。因此，您可以使用递归来计算 gcd(a, b)

当 r == 0 ，这意味着a == bq ，或者 b划分a 。因此，b是 a, b 的最大公约数，也适用于原件a, b 。此时递归调用将保持 b如a和0如b ，所以它的返回 a .

希望这个解释涵盖了所有内容