求最大公约数，一个逐步消除递归的例子。

本文主要是介绍求最大公约数，一个逐步消除递归的例子。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法 stein www.cnblogs.com/drizzlecrj/archive/2007/09/14/892340.html

int gcd (int a, int b) // a,b>=0
{if(a==0) return b;if(b==0) return a;if( ((a&1)==0) && ((b&1)==0) ) {return gcd(a>>1,b>>1)<<1;		}else if((a&1)==0) {a>>=1;}else if((b&1)==0) {b>>=1;}return gcd(abs(a-b),min(a,b));
}

尾递归（就是return 函数本身;）能 很容易地 改成 循环。

return gcd(abs(a-b),min(a,b)); 是尾递归

return gcd(a>>1,b>>1)<<1; 不是尾递归，因为返回的不是函数本身，而是包含它的表达式，这样也不构成 尾递归。

于是得 把它改成 尾递归。如何改？只能更改递归的“接口”了。

int gcd2(int a, int b, int multiple) // 求a b的最大公约数的multiple倍
{if (a == 0) return b*multiple;if (b == 0) return a*multiple;if (((a & 1) == 0) && ((b & 1) == 0)) {return gcd2(a >> 1, b >> 1, multiple << 1);}else if ((a & 1) == 0) {a >>= 1;}else if ((b & 1) == 0) {b >>= 1;}return gcd2(abs(a - b), min(a, b), multiple);
}

如上，已成 尾递归。把尾递归 改为 循环，先 用 goto 代替。

int gcd3(int aa, int bb)
{int a = aa;int b = bb;int multiple = 1;loop:if (a == 0) return b*multiple;if (b == 0) return a*multiple;if (((a & 1) == 0) && ((b & 1) == 0)) {a >>= 1;b >>= 1;multiple <<= 1;goto loop;}else if ((a & 1) == 0) {a >>= 1;}else if ((b & 1) == 0) {b >>= 1;}if (a > b) {a = a - b;}else {b = b - a;}goto loop;
}

把 goto 改写成 while 循环。

int gcd4(int aa, int bb)
{int a = aa;int b = bb;int multiple = 1;while (a&&b){if (((a & 1) == 0) && ((b & 1) == 0)) {a >>= 1;b >>= 1;multiple <<= 1;continue;}else if ((a & 1) == 0) {a >>= 1;}else if ((b & 1) == 0) {b >>= 1;}if (a > b) {a = a - b;}else {b = b - a;}}if (a == 0) return b*multiple;else return a*multiple;
}

这篇关于求最大公约数，一个逐步消除递归的例子。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---