欧几里得扩展算法递归c语言函数

欧几里得扩展算法（Extended Euclidean Algorithm），也称为扩展欧几里得算法，不仅可以用来计算两个正整数a和b的最大公约数（GCD），还可以找到整数x和y，使得ax + by = gcd(a, b)。这个算法是欧几里得算法的扩展，它利用递归或者循环来实现。

在C语言中，可以通过递归的方式来实现扩展欧几里得算法。下面是一个递归函数的示例代码：

#include <stdio.h>

// 递归实现扩展欧几里得算法
int extended_gcd(int a, int b, int *x, int *y) {
    if (b == 0) {
        *x = 1;
        *y = 0;
        return a;
    }
    int x1, y1;
    int gcd = extended_gcd(b, a % b, &x1, &y1);
    *x = y1;
    *y = x1 - (a / b) * y1;
    return gcd;
}

int main() {
    int x, y;
    int a = 60, b = 48;
    int gcd = extended_gcd(a, b, &x, &y);
    printf("gcd(%d, %d) = %d\n", a, b, gcd);
    printf("x = %d, y = %d\n", x, y);
    return 0;
}

这段代码定义了一个名为`extended_gcd`的函数，它接受两个整数`a`和`b`，以及两个指向整数的指针`x`和`y`。函数计算`ax + by = gcd(a, b)`的整数解，并通过指针参数返回`x`和`y`的值。