。

递归在编程学习中可谓是无处不在，计算机的所有运算拆分开都是递归。

比如1+2，可以拆成1+（1+1），同理，所有的加减乘除都可以…目录

一、gcd（求最大公因数）

上次博客本是说这周分享算法的，后来还是想先分享一下递归思想。

递归在编程学习中可谓是无处不在，计算机的所有运算拆分开都是递归。

比如1+2，可以拆成1+（1+1），同理，所有的加减乘除都可以拆成1+1的式子，这就是递归。

给一个拆分的路径，不断地将一个式子递归拆分成一个个小式子，化繁为简。

下面我们用三个经典递归（gcd，hanoi，quicksort）来走进这种思想。

一、gcd（求最大公因数）

求最大公因数，不得不提的就是辗转相除法，也叫欧几里得算法。

具体操作：用两数中的较大数除以较小数，之后以除数作被除数，余数作除数，不断相除，以致最后一次余数等于零，此时除数位上的数就为原来两个数的最大公因数。

第一步：20%12==1......8

此时余数已为0，所以20与12的最大公因数为除数位置上的4，即gcd(20,12)==4、

int

一个条件表达式，x%y==0吗，即余数等于0吗，如果等于，说明此时有我们想要的y值，如果不等于，继续调用gcd函数本身，依次下去，直到求出最大公因数。

好好领悟，只有一行语句（当然也得保证第一次的形参是xy），是不是简化了特别多？

这就是递归奇妙的地方，当你找到某种规律时，递归很有可能就会派上用场。

二、hanoi（描述汉诺塔）