Namaran

Code daily. Without assist.

2026-09-03

gcd_loop.c

#include <stdio.h>

static unsigned gcd(unsigned a, unsigned b) {
    while (b != 0) {
        a = b;
        b = a % b;
    }
    return a;
}

int main(void) {
    printf("%u\n", gcd(12, 18));
    printf("%u\n", gcd(35, 21));
}

gcd は、末尾再帰で書いたユークリッドの互除法 return gcd(b, a % b); を、スタックを積まないようにループへ書き換えたものです。引数も標準入力も使わず、main が gcd(12, 18) と gcd(35, 21) の結果を出力します。いまは 18 と 21 の2行が出力されますが、本来は 6 と 7 です。

Answer

Wrong

while (b != 0) {
    a = b;
    b = a % b;
}

再帰版の gcd(b, a % b) では、2つの引数はどちらも呼び出す前の a と b から計算されます。ループ版は1行目で a を b で上書きするので、2行目の a % b は b % b、つまり常に 0 です。ループは1周で終わり、gcd(12, 18) は最初の b である 18 を、gcd(35, 21) は 21 を返します。

Right

while (b != 0) {
    unsigned r = a % b;
    a = b;
    b = r;
}

a を書き換える前に、a % b を r に取っておきます。新しい a と b がどちらも古い値から計算されるので、ループの1周が再帰版の1回の呼び出しと同じ意味になります。gcd(12, 18) は (18, 12)、(12, 6)、(6, 0) と進んで 6 を返します1。

  1. C の規格は末尾呼び出しの最適化を保証しないので、深い末尾再帰はループに直しておくのが確実です。ただし互除法の再帰は高々数十段なので、gcd に限ればスタックが足りなくなる心配はほとんどありません。