読者です 読者をやめる 読者になる 読者になる

再帰と繰り返し

c アルゴリズム


ふと再帰とそうでない場合がどの程度違うのかが気になって、
最大公約数を求めるものを書いてみたけど、全然時間が変わらなかった。
10000000回でも全然変わらない。GCCの最適化がすごいのかな。
プログラムが簡単過ぎるのかもしれないけど。最適化なしでも全然
変わらないみたいですね。

int gcd_rec(int a, int b)
{
     int tmp;

     tmp = a % b;

     if (tmp == 0) {
          return b;
     }
     else {
          gcd_rec(b, tmp);
     }
}

int gcd_iter(int a, int b)
{
     int tmp;

     tmp = a % b;

     while (tmp != 0) {
          a = b;
          b = tmp;

          tmp = a % b;
     }
     return b;
}