【問題15 その2】再帰を実現するコンピュータの仕組み：完全マスター！ 組み込みC言語プログラミング（17）（1/2 ページ）

C言語のプログラムにおいて、関数が関数内で自分自身を呼び出すことを「再帰」と呼び、whileやforを使わなくても繰り返しのプログラムを書くことができます。再帰を実現するコンピュータの仕組みとともに身につけましょう。

[横田一弘 埼玉県立新座総合技術高等学校 教諭，MONOist]

　本連載では、これから組み込みシステムのプログラミングを学びたい人向けに、C言語を使ったマイコン制御プログラムの“イロハ”を解説していきます。

　毎回少しずつステップアップしていけるよう、本文の最後で問題を出し、次回その解答と解説を紹介していきます。

再帰を使って問題を解こう

　今回は前回に引き続き、問題15の解説をします。

問題15：

基数変換する関数を作ってください。引数には基数変換する整数と基数、基数変換された結果を受け取る文字列の3つを使います。

　基数変換のアルゴリズムに、「数値を基数で割って、その余りを並べる」方法があります。前回掲示したconvert.c（下参照）も、その方法でプログラムを書いています。

#include <stdio.h>
 
int base;
char *p;
 
void convert(char *str, int num, int base);
void _convert(int num);
 
void main(void)
{
    int n, b;
    char str[33];
 
    printf("数値を入力してください->");
    scanf("%d", &n);
    printf("基数を入力してください->");
    scanf("%d", &b);
    convert(str, n, b);
    printf("%d進数では%sです¥n", b, str);
}
 
void convert(char *s, int num, int b)
{
    base = b;
    p = s;
    if (num == 0)
        *p++ = '0';
    else
        _convert(num);
    *p = '¥0';
}
 
void _convert(int num)
{
    static char NUM[] = "0123456789abcdef";
 
    if (num >= base) _convert(num / base);
    *p++ = NUM[num % base];
}

convert.c

　convert.cで、基数変換はconvertにより計算されます。convertは、numに与えた数値を、bに与えた基数で基数変換し、結果としてsに文字列を格納します。

void convert(char *s, int num, int b)
{
    base = b;
    p = s;
    if (num == 0)
        *p++ = '0';
    else
        _convert(num);
    *p = '¥0';
}

　そして、convertはさらに_convertを呼び出します。基数変換アルゴリズムは _convertに書かれていて、convertは外部変数のbaseとpに、それぞれ基数と文字列の先頭ポインタを代入して、基数変換は_convertに任せます。

void _convert(int num)
{
    static char NUM[] = "0123456789abcdef";
    if (num >= base) _convert(num / base);
    *p++ = NUM[num % base];
}

　さて、_convertは内部で自分自身、すなわち_convertを呼び出していることが分かります。このようなプログラムの構造を「再帰」と呼びます。

　_convertでは、「numを基数で割る」処理をnumが基数より小さくなるまで繰り返し実

行します。再帰呼び出しの条件であるif文がそれで、_convertを再帰呼び出しするときは、numをbaseで割っているので、いずれbaseより小さい値となって再帰呼び出しが終わる構造です。このように、再帰を用いると、whileやforを使わなくても繰り返しのプログラムを書くことができます。

　また「また奇数で割った余りを並べる」処理を、_convertでは再起呼び出しの後に実

行します。convert.cでは、

 *p++ = NUM[num % base];

　により余りを求め文字に変換していますが、この文は再帰呼び出しの後ろに書かれているため、深く呼び出されたものから先にpへと代入されるのです。

　基数変換のアルゴリズムでは、後に計算した余りを先に出力しなければなりません。このような場面でも再帰が生かされます。