以欧几里得算法为例去理解看似不可思议的递归过程

递归的思想就是将复杂的问题转化为简单的问题去解决，即“大事化小”，但递归的实现过程特别是程序编写上简化了繁琐的递推计算，导致代码上难以看懂，甚至感觉不可思议。下面以欧几里得算法为例来逐步理解递归过程。

描述：欧几里得算法用于计算两个正整数的最大公约数，其过程为：给定两个数a和b，用较大的数反复减去较小的数，直到得到的差c小于b，然后用b反复减去c，直至最后两个数字相等为止。那么，最终得到相等的这个数即为原a和b的最大公约数。

比如：a为1247，b为493，则1247-493=754，754-493=261（即c），反转493-261=232，反转261-232=29，反转232-29=203，203-29=174，174-29=145，145-29=116，116-29=87，87-29=58，58-29=29，即最终的29为1247与493的最大公约数。

编写程序过程：

1.递归终止条件为最终两个数相等；

2.两个数如果不相等，则反复相减。

知道这两个条件后，可以编写函数int Eu(int a,int b),假设a为其中大的一个数，则递归调用函数Eu(a-b,b)，当a减去n次b后，得到c小于b，则调用Eu(c,b-c)，不需考虑具体的调用过程，递归函数如下：

int Eu(int a,int b)
{
\tif(a==b)
\t\treturn a;
\telse if(a>b)
\t\treturn Eu(a-b,b);
\telse
\t\treturn Eu(a,b-a);
}

完整验证程序如下：

#include <iostream>
using namespace std;
int Eu(int a,int b);
int main()
{
\tint a,b;
\tcin>>a>>b;
\tcout<\t
\treturn 0;
}
int Eu(int a,int b)
{
\tif(a==b)
\t\treturn a;
\telse if(a>b)
\t\treturn Eu(a-b,b);
\telse
\t\treturn Eu(a,b-a);
}
/<iostream>