一、求两个数的最大公约数
如何编程计算N个数的最大公约数（Greatest common divisor）呢？第一想法那便是两两计算，但是往往最简单的想法是不怎么靠谱的。下面用递归来解决。递归有一大好处，那便是递归非常符合人的思维，有时即使很复杂，但是依仗着递归的规律性，可以断定或推测出按递归做是正确的。如果说递归的性能低，我们可以采用备忘录法，用表记录过已经计算过的问题，避免二次计算，这样在一定程度上可以带来性能上的提升。我们可以先用递归实现，倘若在实际情况中发现性能问题，我们可以再进行优化。但是如果一开始的代码就是在考究性能，甚至考虑到用位运算等等，那么再修改程序时，那会非常困难，也许过了一段时间后，自己一下子也会读不懂自己写的代码了。“过早优化是万恶之源”。我认为，在这个时代，把代码写的很清楚，流程很明朗，这应该是我们追求的，这样可以体现出你的思考过程。
用辗转相除法求公约数
1 /**
2 * 求两个数的最大公约数
3 * @param a
4 * @param b
5 * @return
6 */
7 public int getGCDInTwo(int a,int b)
8 {
9 if(b==0)
10 {
11 return a;
12 }
13 else
14 {
15 return getGCDInTwo(b,a%b);
16 }
17 }
二、求N个数的最大公约数
用递归的思想来思考，我们可以这样想，要求N个数的最大公约数，我们可以求第N个数和[其余N-1个数的最大公约数]的公约数，要求N-1个数的最大公约数，我们可以求第N-1个数和[其余N-2个数的最大公约数]的公约数…………如此递归下去，直到N值为1，这时停止递归，返回元素值（这时仅有一个元素），接下去那便是pop栈，最后计算出结果。代码如下(要用到以上辗转相除法求公约数的代码)：
1 /**
2 * 求N个数的最大公约数
3 * @param arr
4 * @param len：len为求数组中前len个数的最大公约数
5 * @return
6 */
7 public int getGCDInN(int[] arr,int len)
8 {
9 if(len==1)
10 {
11 return arr[0];
12 }
13 else
14 {
15 return getGCDInTwo(arr[len-1],getGCDInN(arr,len-1));
16 }
17 }
三、总结
平时我们应当养成用递归思考问题的习惯，因为递归非常符合人的思维，递归有时会让你很惊喜。