換個方式看公因數

Q : 輸入兩個正整數，以遞迴方式計算最大公因數並輸出

在 "遞迴尋找公因數" 中，雖然使用了遞迴函式來尋找公因數，但其運算方式和使用for迴圈並無不同，執行效率也沒有提升，純粹只是為了要寫成遞迴的型式。

若有 a b 兩數的公因數是 7，表示 a 和 b 必為 7 的倍數，如 7*3=21 與 7*5=35，則兩數相減的差也必然是 7 的倍數，展開來看就很清楚：

35-21=(7*5)-(7*3)=7*(5-3)=14，7當然也是14(兩數相減)的因數

反覆利用兩數相減的差，取代原先大的數字來尋找公因數，可減少測試的次數(先前的方式是每次減1，遞減速度較慢)，而遞迴函式即適合用來處理這類的運算，程式如下

#include <iostream>

int common_divisor(int a, int b)
{
   if(a%b==0) //如果a/b餘0，b就是公因數
      return b;
   else if(a>b)
      return common_divisor(a-b,b); //a值較大，把a減掉b繼續測試
   else
      return common_divisor(b,a); //b值較大，交換位置重新測試
}

int main()
{
    int a, b;

    std::cout << "請輸入2個正整數:";
    std::cin >> a >> b;
    std::cout << "最大公因數=" << common_divisor(a,b);
    return 0;
}

若要處理更多個數字，則可以搭配先前的方法來處理

#include <iostream>

int common_divisor(int a, int b) //遞迴函式1 
{
   if(a%b==0) //如果a/b餘0，b就是公因數
      return b;
   else if(a>b)
      return common_divisor(a-b,b); //a值較大，把a減掉b繼續測試
   else
      return common_divisor(b,a); //b值較大，交換位置重新測試
}

int common_divisor(int d[], int n) //遞迴函式2 
{
   if(n==2)
     return common_divisor(d[0],d[1]); //只剩兩個數字，交給遞迴函式1找公因數 
   else if(n>2)
     //提出第一個數字，第二個數字由遞迴函式2處理，再交給遞迴函式1找公因數
     return common_divisor(d[0], common_divisor(&d[1], n-1));

   return 0; //n小於2才會發生 
}

int main()
{
    int data[1000], datacount=0; //假設輸入數字最多1000個

    std::cout << "請輸入n個正整數，輸入完成請按 Ctrl-Z" << std::endl; 
    while ( std::cin >> data[datacount] )
        datacount++;
  
    std::cout << "最大公因數=" << common_divisor(data, datacount);
    return 0;
}

最後，使用二分法來改寫遞迴函式2，可以讓程式的執行效率更好

int common_divisor(int d[], int n) //遞迴函式2
{
   if(n==1)
     return d[0];
   if(n==2)
     return common_divisor(d[0],d[1]);
   if(n>2)
     return common_divisor(common_divisor(d,n/2),
                                        common_divisor(&d[n/2],n-n/2) );

   return 0; //n小於1才會發生
}