c语言求最大公约数递归与非递归算法对比

写 C 语言求最大公约数的时候，你是不是也纠结过？老师说递归代码简洁，同学说非递归不容易出错，到底该用哪个？新手常常看着两种写法发呆，递归的函数自己调自己，绕来绕去理不清逻辑；非递归的循环倒是直观，可又觉得不够 “高级”。其实啊，递归和非递归各有各的好，今天兔子哥就把这两种算法拆开来比一比，从代码到用法，清清楚楚告诉你该怎么选，一起往下看吧！

---

先搞懂：递归和非递归，到底啥区别？

递归说白了，就是函数自己调用自己，把大问题拆成小问题，直到碰到终止条件才停下来。比如求最大公约数的递归写法，就是不断用除数和余数调用自己，直到余数为 0。
非递归呢，就是用循环来实现，比如 while 循环，一步步算余数，更新除数和被除数，直到余数为 0。不用函数自己调用自己，逻辑都在循环里走。
打个比方，递归就像剥洋葱，一层一层剥下去，剥到最里面（终止条件）就知道结果了；非递归像爬楼梯，一步一步往上走，走到顶就到终点了。两种方法都能到目的地，只是走的路不一样。

---

递归算法怎么写？代码简单但得注意终止条件

递归求最大公约数，核心还是辗转相除法，只是把循环换成了函数自调。咱们直接看代码：
c运行

#include // 递归求最大公约数int gcd_recursive(int a, int b) {// 处理负数，转成正数if (a < 0) a = -a;if (b < 0) b = -b;// 终止条件：余数为0时，返回除数if (b == 0) {return a;} else {// 自己调用自己，参数换成b和a%breturn gcd_recursive(b, a % b);}}int main() {int num1, num2;printf("输入两个数：");scanf("%d %d", &num1, &num2);printf("最大公约数（递归）：%d\n", gcd_recursive(num1, num2));return 0;}

你看，递归代码确实短，去掉注释没几行。但有个大问题：如果两个数特别大，递归调用的次数就会很多，可能超过系统允许的函数调用栈深度，程序就会崩溃，这就是所谓的 “栈溢出”。比如求两个 10 亿以上的数，递归说不定就扛不住了。

---

非递归算法怎么写？循环直观但代码稍长

非递归用 while 循环实现，逻辑和递归一样，只是把自调换成了循环里更新参数。代码是这样的：
c运行

#include // 非递归求最大公约数int gcd_non_recursive(int a, int b) {int temp;// 处理负数if (a < 0) a = -a;if (b < 0) b = -b;// 循环代替递归，直到b为0while (b != 0) {temp = a % b;a = b;b = temp;}return a;}int main() {int num1, num2;printf("输入两个数：");scanf("%d %d", &num1, &num2);printf("最大公约数（非递归）：%d\n", gcd_non_recursive(num1, num2));return 0;}

非递归的代码稍长一点，但逻辑更直观，一步一步更新 a 和 b 的值，不容易出错。而且循环不会有栈溢出的问题，就算处理很大的数，只要循环次数够，就能算出结果。新手刚开始写，可能更容易理解循环的过程，递归的自调总让人绕不过来。

---

递归和非递归对比表，一目了然

对比项	递归算法	非递归算法
代码长度	短，简洁	稍长，步骤清晰
理解难度	难，需理解自调逻辑	易，循环过程直观
内存占用	高，每次调用占栈空间	低，只有几个变量
适用场景	中小数字，代码追求简洁	大数字，要求稳定
常见错误	忘了写终止条件，栈溢出	循环条件写错，死循环

比如写作业的时候，数字不大，用递归显得代码干净；要是做项目，处理的数据可能很大，非递归就更靠谱。

---

为啥递归容易出错？新手常踩的坑

递归的坑主要在终止条件上。比如把if (b == 0) return a;写成if (a == 0) return b;，看起来差不多，其实会出问题。假设 a=0，b=5，正确结果是 5，要是写成 a==0，返回的就是 b，这时候是对的；但如果 a=5，b=0，就会返回 0，这就错了。所以终止条件必须是判断除数（b）是否为 0。
非递归的坑多在循环条件。比如把while (b != 0)写成while (a != 0)，当 b 变成 0 后，a 的值不变，循环就停不下来，程序直接卡死。新手写循环的时候，一定要想清楚什么时候该结束。

---

可能有人会问，递归既然可能栈溢出，为啥还要学它？其实递归在某些场景下特别好用，比如树的遍历、斐波那契数列，代码能写得很简洁。求最大公约数用递归，主要是为了理解递归的思想，实际用的时候，还是得看情况。
兔子哥刚开始学的时候，总觉得递归很 “高级”，写啥都想用递归，结果有次处理大数字，程序崩了才知道栈溢出这回事。后来就养成习惯，简单场景、小数据用递归，正式项目里尽量用非递归，稳当。
其实啊，不管递归还是非递归，能算出正确结果的就是好方法。新手不用急着追求哪种更厉害，先把两种写法都练熟，知道它们的优缺点，用到的时候自然就知道该选哪个了。多试试不同的数字，比如很大的数、负数，看看两种方法的表现，慢慢就有感觉了。希望这些能帮到你，下次写代码的时候，心里就有数了！

标签： 清清楚楚 比一比