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