NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 23 题

#include <iostream>
using namespace std;

int a,b;

int work(int a,int b){
	if (a%b)
		return work(b,a%b);
	return b;
}

int main(){
	cin >> a >> b;
	cout << work(a,b) << endl;
	return 0;
}

输入：123 321 输出：_________

这题考递归与辗转相除法的结合。拿到题先别急着按计算器，盯着 return 条件想：a%b 等于 0 时停，否则参数交换继续。输入 123 和 321，第一层发现 123%321 还是 123，直接交换变成 work(321,123)，后面就按欧几里得算法一步步除余，最后余数为 0 时返回的除数就是答案。

很多同学习惯先算 321%123=75，却忽略了代码里第一句是 a%b，也就是 123%321，结果不会触发递归交换，直接返回 123 就错了。还有人以为递归会无限套娃，其实只要记住终止条件里 a%b 为 0 就停，并且每次调用里 a 始终是原来的 b，b 始终是原来的余数，这样就能心算出结果。

这题考什么

这道题考查的是递归函数与最大公约数（GCD）的欧几里得算法（辗转相除法）的结合。命题人把经典的数学算法封装成递归函数，再放进一个简单的输入输出框架里，目的很明确：看你能不能读懂递归的终止条件，以及能否在脑子里模拟出参数交换后的层层调用。

知识点人话版

递归函数

递归就是函数自己调用自己。每次调用时，函数会先检查一个终止条件（比如 if (a%b)），如果条件不成立（即 a%b 等于 0），就返回结果；如果条件成立，就带着新的参数再调用一次自己，直到某一次调用满足终止条件为止。

辗转相除法（欧几里得算法）

求两个正整数 a 和 b 的最大公约数，有一个非常古老的定理：

gcd(a, b) = gcd(b, a mod b)

意思是：两个数的最大公约数，等于其中较小的数和较大数除以较小数余数的最大公约数。反复用这个规则，余数会越来越小，直到余数为 0，此时除数就是最大公约数。