以歐幾里得算法為例去理解看似不可思議的遞歸過程

遞歸的思想就是將複雜的問題轉化為簡單的問題去解決，即“大事化小”，但遞歸的實現過程特別是程序編寫上簡化了繁瑣的遞推計算，導致代碼上難以看懂，甚至感覺不可思議。下面以歐幾里得算法為例來逐步理解遞歸過程。

描述：歐幾里得算法用於計算兩個正整數的最大公約數，其過程為：給定兩個數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>