資料結構 Greatest common divisor(最大公因數)

GCD是耳熟能詳的一種遞迴方法，中文意思是『求最大公因數』
求最大公因數再小學的時候就有交過，有一種方法就是透過輾轉相除法
透過輾轉相除法不斷的對除，最後解即為最大公因數

程式碼如下：

#include <stdio.h>

int count = 0;

int GCD(int a, int b){
        count++;

        if(a % b == 0)  return b;
        else return GCD(b, a % b);
}

int main()
{
        printf("Number:%d\n", GCD(120, 45));
        printf("Count:%d\n", count);

        return 0;
}

執行結果如下：

那當然我會手賤的將

printf("Number:%d\n", GCD(120, 45));

改成

printf("Number:%d\n", GCD(45, 120));

那Count又增加一次了，有興趣的人可以深入探討一下該遞迴含式

參考資料：
https://en.wikipedia.org/wiki/Greatest_common_divisor
http://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95
https://zh.wikipedia.org/zh-tw/%E6%9C%80%E5%A4%A7%E5%85%AC%E5%9B%A0%E6%95%B8