【C言語】再帰関数を使って数値を反転するプログラムの書き方

「再帰関数(recursive function)」とは、関数の処理の中で自分自身を再度呼び出す関数のことです。再帰を活用すると、繰り返しの処理を簡潔に記述できるのが大きな特徴です。

再帰関数の基本：階乗計算を例に

再帰の仕組みを理解するために、最もよく知られた例である「階乗(階乗値)」の計算を見てみましょう。

• fact() 関数は、整数 N の階乗(1 から N までのすべての整数の積)を計算します。
• 引数が 1 または 0 の場合、関数は 1 を返します(基底ケース)。それ以外の場合は n × fact(n-1) を返し、n が 1 になるまで自分自身を呼び出し続けます(再帰ケース)。

Fact(5) = 5 × fact(4)
        = 5 × 4 × fact(3)
        = 5 × 4 × 3 × fact(2)
        = 5 × 4 × 3 × 2 × fact(1)
        = 5 × 4 × 3 × 2 × 1
        = 120

例1:再帰関数による階乗の計算

以下は、再帰関数を使って階乗を求めるC言語のプログラムです。

#include <stdio.h>

int fact(int n);

int main(void) {
    int n, f;
    printf("数字を入力してください: ");
    scanf("%d", &n);
    f = fact(n);
    printf("階乗の値 = %d\n", f);
    return 0;
}

int fact(int n) {
    if (n == 1 || n == 0)
        return 1;                /* 基底ケース */
    else
        return n * fact(n - 1);  /* 再帰ケース */
}

実行結果

数字を入力してください: 5
階乗の値 = 120

例2:再帰関数で数値を反転する

続いて、再帰関数を使って入力された数値を反転させるC言語のプログラムを紹介します。このプログラムでは、次の手順で桁を逆順に組み立てていきます。

1. num % 10 で最下位の桁(余り)を取り出す
2. sum = sum × 10 + 余り で、それまでの結果を1桁ずらして新しい桁を追加する
3. num / 10 で最下位の桁を取り除き、残りの数値に対して自分自身を再帰的に呼び出す
4. num が 0 になった時点で再帰を終了し、累積した sum を返す(基底ケース)

#include <stdio.h>

int sum = 0, rem; /* グローバル変数 */

int revNumFunction(int num);

int main(void) {
    int num, revNum;
    printf("数字を入力してください:\n");
    scanf("%d", &num);
    revNum = revNumFunction(num); /* 数値を反転する関数を呼び出し */
    printf("反転後の数値: %d\n", revNum);
    return 0;
}

int revNumFunction(int num) {
    if (num == 0)                    /* 基底ケース:全桁の処理が完了 */
        return sum;
    rem = num % 10;                  /* 最下位の桁を取り出す */
    sum = sum * 10 + rem;            /* 桁をずらして新しい桁を追加 */
    return revNumFunction(num / 10); /* 残りの桁で再帰呼び出し */
}

実行結果

数字を入力してください: 1357
反転後の数値: 7531

処理の流れ(1357 の場合)

1357 % 10 = 7 → sum = 0 × 10 + 7   = 7
 135 % 10 = 5 → sum = 7 × 10 + 5   = 75
  13 % 10 = 3 → sum = 75 × 10 + 3  = 753
   1 % 10 = 1 → sum = 753 × 10 + 1 = 7531
   0 → 再帰終了、7531 を返す

まとめ

再帰関数を正しく動作させるには、「基底ケース(再帰を終了する条件)」と「再帰ケース(自分自身を呼び出す処理)」の2つの要素が不可欠です。基底ケースがないと無限に呼び出しが続き、スタックオーバーフローを引き起こすため注意しましょう。

数値の反転のように、桁ごとの処理を繰り返す問題は再帰と相性が良く、ループを使った実装よりもコードを簡潔に記述できるのがメリットです。ぜひ階乗やフィボナッチ数列など、他の問題でも再帰の考え方を試してみてください。