帮我讲一下这个程序的递归流程 看得有些晕

来源:百度知道 编辑:UC知道 时间:2024/06/17 18:43:36
int exGcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int r = exGcd(b, a % b, x, y);
int t = x;//哪里的x?看的晕了
x = y;
y = t - a / b * y;

return r;
}

这个程序的返回值是a,b的最大公约数.

int exGcd(int a, int b, int &x, int &y)
{
if(b == 0)
{
x = 1;
y = 0;
return a;
}
int r = exGcd(b, a % b, x, y);
int t = x;//这里的x,是调有了上面exGcd()后的x值.x,y由a,b确定.
//不由调者确定.因为递归调用栈顶最后一层调用会给x,y赋初值1,0.
//这个X,Y似乎没有什么意义,要看使用的环境才能定.
x = y;
y = t - a / b * y;

return r;
}