23、递归与数学：最大公约数（辗转相除法）的递归实现

最大公约数，英文叫 GCD（Greatest Common Divisor）。

这东西在数学里很基础，但在编程里，它经常出现在一些意想不到的地方。比如分数约分、RSA 加密算法、甚至一些图形学的底层计算。我个人习惯，遇到这类数学问题，先想想能不能用递归搞定——因为数学公式本身，往往就是递归的。

辗转相除法：老祖宗的智慧

辗转相除法，也叫欧几里得算法。它的核心思想其实就一句话：

两个数的最大公约数，等于其中较小的数和两数相除余数的最大公约数。

用数学公式写出来就是：

gcd(a, b) = gcd(b, a % b)

一直算下去，直到余数为 0。这时候，另一个数就是最大公约数。

举个例子：求 48 和 18 的最大公约数。

• 48 ÷ 18 = 2 余 12 → gcd(48, 18) = gcd(18, 12)
• 18 ÷ 12 = 1 余 6 → gcd(18, 12) = gcd(12, 6)
• 12 ÷ 6 = 2 余 0 → gcd(12, 6) = 6

所以 gcd(48, 18) = 6。

你想想看，这个过程是不是天然就是递归的？每次把问题规模缩小一点，直到遇到一个可以直接返回的边界条件。

递归实现：三行代码搞定

有了上面的公式，写递归就很简单了。我直接上代码：

#include <stdio.h>

// 递归实现辗转相除法
int gcd(int a, int b) {
    if (b == 0) {
        return a;  // 边界条件：余数为0，返回a
    }
    return gcd(b, a % b);  // 递归调用
}

int main() {
    int x = 48, y = 18;
    printf("gcd(%d, %d) = %d\n", x, y, gcd(x, y));
    return 0;
}

运行结果：

gcd(48, 18) = 6

嗯，就这么简单。递归函数的核心就两个部分：

• 边界条件：b == 0 时，直接返回 a。这是递归的出口。
• 递归调用：gcd(b, a % b)，把问题规模缩小。

我在项目中遇到过一个问题：有人写递归时，边界条件写成了 if (a == 0) return b;。这其实也可以，但要注意参数顺序。两种写法本质一样，只是习惯不同。我个人习惯用 if (b == 0) return a;，因为这样更符合数学公式的直觉。

递归的调用过程：画个图就明白了

为了让你更清楚递归是怎么一层层展开又收回的，我画了一张流程图：

你看，递归就是一层层往下「递」，直到碰到边界条件，然后一层层往回「归」。每次返回的都是当前这层的计算结果。

避坑指南：我曾经踩过的坑

我曾经在写这个函数时，犯过一个低级错误——参数顺序写反了。你猜怎么着？

// 错误写法
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(a % b, b);  // 参数顺序错了！
}

这样写，如果 a < b，第一次递归就变成 gcd(a % b, b) = gcd(a, b)，然后无限递归，栈溢出。嗯，程序直接崩了。

非递归版本：对比一下

当然，这个算法也可以用循环实现。我贴出来给你对比一下：

int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

两种写法，逻辑完全一样。区别在于：

• 递归版：代码简洁，数学直觉强，但会消耗栈空间。
• 循环版：效率更高，没有函数调用开销，适合嵌入式等资源受限场景。

我个人建议：在理解算法原理时用递归版，在生产代码中如果递归深度不大也可以用递归版。但如果要处理超大整数，或者对性能有极致要求，还是用循环版稳妥。

扩展：处理负数

辗转相除法默认处理的是正整数。如果输入有负数呢？

其实很简单：最大公约数通常定义为正数。所以可以先取绝对值，再计算。

int gcd_safe(int a, int b) {
    a = (a < 0) ? -a : a;
    b = (b < 0) ? -b : b;
    return gcd(a, b);
}

或者更简洁一点，用 abs() 函数：

#include <stdlib.h>

int gcd_safe(int a, int b) {
    return gcd(abs(a), abs(b));
}

总结一下

辗转相除法的递归实现，是理解「递归与数学关系」的绝佳例子。它告诉我们：

• 数学公式本身就是递归的，直接翻译成代码就行。
• 边界条件要写对，否则要么死循环，要么结果错误。
• 递归不是万能的，但在这个场景下，它让代码变得极其优雅。

说白了，递归就是「用自己定义自己」。你只要找到那个不变的规律（递推关系），再找到那个停下来的条件（边界），剩下的交给计算机去跑就行了。

下次你遇到数学问题，不妨先想想：能不能用递归？

---

公众号:蓝海资料掘金营，微信deep3321