Namaran

Code daily. Without assist.

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。

  1. rev は末尾呼び出しなので、コンパイラは呼び出しをジャンプに置き換え、スタックを積まずに済ませられます。ただし C の規格はこの最適化を求めておらず、最適化なしのビルドでは rev も same と同じ深さまでフレームを積みます。