企业网站 .net广州冼村事件
目录
一、gcd（求最大公因数）
二、hanoi（描述汉诺塔）
三、quicksort（快排）
上次博客本是说这周分享算法的，后来还是想先分享一下递归思想。递归在编程学习中可谓是无处不在，计算机的所有运算拆分开都是递归。比如1+2，可以拆成1+（1+1），同理，所有的加减乘除都可以拆成1+1的式子，这就是递归。给一个拆分的路径，不断地将一个式子递归拆分成一个个小式子，化繁为简。
下面我们用三个经典递归（gcd，hanoi，quicksort）来走进这种思想。
一、gcd（求最大公因数）
求最大公因数，不得不提的就是辗转相除法，也叫欧几里得算法。具体操作：用两数中的较大数除以较小数，之后以除数作被除数，余数作除数，不断相除，以致最后一次余数等于零，此时除数位上的数就为原来两个数的最大公因数。
拿一个具体的例子来说：求20与12的最大公因数。
第一步：20%12==1......8
第二步：12%8==1......4
第三步：8%4==2......0
此时余数已为0，所以20与12的最大公因数为除数位置上的4，即gcd(20,12)==4、
那么用代码如何去实现呢？根据直观感受，我们可以这样写：
int gcd(int x, int y)//自定义函数，确保两数中，x>y
{int yu = x % y;//余数while (yu)//循环至余数等于零{x = y;y = yu;yu = x % y;}return y;//此时的除数就为最大公因数
}但结合除数一定大于余数的知识和递归思想，我们却能进一步简化：
int gcd(int x, int y)
{return x % y == 0 ? y : gcd(y,x%y);
}一个条件表达式，x%y==0吗，即余数等于0吗，如果等于，说明此时有我们想要的y值，如果不等于，继续调用gcd函数本身，依次下去，直到求出最大公因数。好好领悟，只有一行语句（当然也得保证第一次的形参是x>y），是不是简化了特别多？这就是递归奇妙的地方，当你找到某种规律时，递归很有可能就会派上用场。