遞迴尋找公因數

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

在 "求最大公因數" 中，求公因數的函式裡有一個 for 迴圈

把這段改為遞迴就行了

#include <iostream>

int common_divisor(int a, int b, int c, int x) //遞迴函式
{
if(a%x==0 && b%x==0 && c%x==0) //終止條件，找到公因數 
return x;

x--;
if (x>a) x=a;
if (x>b) x=b;
if (x>c) x=c;

return common_divisor(a,b,c,x); //測試下一個 
}

int common_divisor(int a, int b, int c)
{
return common_divisor(a,b,c,a); //先假設a是公因數，去呼叫遞迴函式
}

int main()
{
  int a, b, c;

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

這個程式中有兩個同名函式 common_divisor，這是 C++ 允許的，因為兩個函式接受參數的數量不同，所以編譯器會依呼叫者所傳遞的參數數量(和型態)，去對應正確的函式。在 main 裡的 std::cout << "最大公因數=" << common_divisor(a,b,c); 因只傳了 a,b,c 三個參數，所以會呼叫非遞迴的 int common_divisor(int a, int b, int c)，再透過這個函式呼叫真正的遞迴函式 int common_divisor(int a, int b, int c, int x) 去尋找答案。

上面的程式裡有個明顯的問題，由於最大公因數 x 必小於或等於 a b c，為了避免多餘的運算，所以在遞迴函式中有 x>a x>b x>c 的判斷，以快速縮小 x 的起始值來提升運算的效率，但 x>a x>b x>c 的判斷只需在開始時執行一次就可以了，不用在每次遞減的過程中重複進行無效比對，程式修改如下：

int common_divisor(int a, int b, int c, int x) //遞迴函式
{
if(a%x==0 && b%x==0 && c%x==0) //終止條件，找到公因數 
return x;

return common_divisor(a,b,c,x-1); //遞減測試下一個 
}

int common_divisor(int a, int b, int c)
{
  int x=a;
if (x>b) x=b;
if (x>c) x=c;
return common_divisor(a,b,c,x); //先假設a b c中最小的是公因數，去呼叫遞迴函式
}