2026-09-03
reverse_digits.c
#include <stdio.h>
static int rev(int n, int acc) {
if (n == 0)
return acc;
return rev(n / 10, acc * 10 + n % 10);
}
static int same(int n) {
if (n == 0)
return 0;
return same(n / 10) * 10 + n % 10;
}
int main(void) {
printf("%d %d\n", rev(1230, 0), same(1230));
}
これは何を出力するでしょうか?
Answer
321 1230 です。
どちらの関数も n を10で割りながら4回自分を呼び、n が 0 になったところで折り返します。2つの違いは、桁を組み立てる掛け算を呼び出しの前にするか、後にするかです。
rev の再帰呼び出しは関数の最後の処理、つまり末尾呼び出しです。acc * 10 + n % 10 は呼び出しの前に計算されるので、下の桁から取り出したそばから acc に積まれていきます。acc は 0、3、32、321 と進み、いちばん深い呼び出しがこの値をそのまま返します。最初に取り出した桁は 0 で、0 * 10 + 0 は 0 のままです。int には先頭の0を覚えておく場所がないので、0321 ではなく 321 になります。
same は same(n / 10) から戻ってきたあとで * 10 + n % 10 を計算するので、末尾呼び出しではありません。各段は自分の n % 10 を覚えたまま待ち、いちばん深い段の 0 から戻るたびに 1、12、123、1230 と組み上がります。上の桁ほど先に積まれるので、桁の順は元のままです1。
revは末尾呼び出しなので、コンパイラは呼び出しをジャンプに置き換え、スタックを積まずに済ませられます。ただし C の規格はこの最適化を求めておらず、最適化なしのビルドではrevもsameと同じ深さまでフレームを積みます。