itoa関数の再帰版の実装

K&R本 演習4-12

printdのアイデアを使ってitoaの再帰版を書け。すなわち、再帰ルーチンを呼ぶことによって整数を文字列に変換せよ。

再帰を使って変換ですか。面白そうですね。

#include <stdio.h>

void myitoa (int n,char *s) {
    if(n){
        int i = 0;
        int l = n;
        while(l/=10){ i++; }
        myitoa(n/10,s);
        s[i] = n % 10 + '0';
        s[i+1] = '\0';
    }
}

int main (void) {
    char str[100];
    int n = 456;
    
    myitoa(n,str);
    printf("%s",str);
}

こんなに短いコードなのに1時間以上格闘してましたorz

何度も考えて書き直した結果、まず最初にnの桁数をiに取得しておいて、そのiの部分から代入していくようにしました。

代入はmyitoa関数を再帰呼び出しするよりも後にするのがポイントです。

何故なら先に代入してしまうと、代入が全て終了した時点でsの位置が0要素目になってしまうからです。

つまり、\0を代入するタイミングがなくなってしまうということです。

わかりやすいようにprintfを入れてみます。

void myitoa (int n,char *s) {
    if(n){
        int i = 0;
        int l = n;
        while(l/=10){ i++; }
        myitoa(n/10,s);
        s[i] = n % 10 + '0';
        s[i+1] = '\0';
        printf("i=%d s=%s\n",i,s); 
    }
}

$ main
i=0 s=4\0
i=1 s=45\0
i=2 s=456\0

こうなります。要素を追加しつつ追いかけるように\0を代入できます。

しかし、これがもし逆だったら

void myitoa (int n,char *s) {
    if(n){
        int i = 0;
        int l = n;
        while(l/=10){ i++; }
        s[i] = n % 10 + '0';
        s[i+1] = '\0';
        printf("i=%d s=%s\n",i,s); 
        myitoa(n/10,s);
    }
}

$ main
i=2 s=ﾄ06\0
i=1 s=ﾄ5\0
i=0 s=4\0

こうなるので、\0の代入によって上書きされてしまい、うまくいかないのです。

といった感じであれこれやってたら1時間以上もかかってしまったというわけなのです。しくしく。

でも色々と勉強になったので良しとします。