Integer-to-string conversion using recursion

Question

Adapt the ideas of printd to write recursive version of itoa; that is, convert integer into a string by calling a recursive routine

Here is the implementation of printd:

void printd(int n) {
    if(n < 0)
        putchar('-');
    if(n / 10)
        printd(n / 10);
    putchar(n % 10 + '0')l
}

And here is my solution:

int itoa(int n, char s[]) {
    int i;

    if(n < 0) {
        n *= -1; 
    }

    i = 0;
    if(n / 10) {
        i = itoa(n / 10, s);
    }
    s[i] = n % 10 + '0';
    s[++i] = '\0';

    return i; /* next free slot in array */
}

As you can see, my version of itoa is a little bit different than the one presented in the book. It returns a variable i that represents the index of the next free slot in array, at every step it fills the next empty slot with the null character. At the deepest level of recursion, it returns 1.

Could you review my exercise?

Answer 1

There are two bugs in printd():

1. The last character is an l instead of a semicolon.
2. If n is negative, it prints a negative sign before each digit.

Your itoa() also has a bug in handling negative input. It always stringifies the absolute value of n.

Your strategy to use the return value to determine which array element to write to seems like a good idea. I think it would be more user friendly, though, to say that you are returning the strlen() of the output.

int itoa(int n, char s[]) {
    int i = 0;

    if (n < 0) {
        s[0] = '-';
        return 1 + itoa(-n, s + 1);
    }

    if (n / 10) {
        i = itoa(n / 10, s);
    }
    s[i] = n % 10 + '0';
    s[++i] = '\0';

    return i; /* strlen(s), i.e. the next free slot in array */
}

Answer 2

The signature of itoa is supposed to look like this:

char* itoa( int value, char* str, int base);

Therefore, if you want your recursing function to return a int, then you can call it as a private subroutine (a non-public implementation detail of your public itoa function).

static int itoa_implementation(int n, char s[]) { ... }

char* itoa( int value, char* str, int base)
{
    itoa_implementation(value, str); // don't care about the int return code
    return str; // as expected/required of the standard itoa function
}

You should also modify your implementation to support the int base parameter (which you'll probably find easy to do):

• Your current implementation assumes the base is (hard-coded) 10
• Your current n % 10 + '0' expression should be modified to potentially return 'a', 'b', etc., if the base is larger than 10.

Answer 3

1. printd() look fine except for negative numbers (@200_success). Following may fix

    putchar((abs(n) % 10 + '0');
   

2. @ChrisW well pointed out that if one is to use the name of a common function like itoa(), code should function in a similar fashion.

3. if(n / 10) { i = itoa(n / 10, s); computes n/10 twice. Suggest calculating once and saving the result. Being a / operation, I`d expect a slight performance improvement.

4. if(n < 0) { n *= -1; } has problems when n == INT_MIN and 2's complement (which is the usual signed integer format). The only portable solution I can think of is to embrace the negative side instead of the positive side as follows:

   // value is <= 0
   static char *itoa_recursive_helper(int value, char* str, int base) {
     if (value <= -base) {
       str = itoa_recursive_helper(value / base, str, base);
       value %= base;
     }
     *str++ = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[-value];
     *str = '\0';
     return str;
   }
   
   char* itoa_recursive(int value, char* str, int base) {
     // Could add checks here for str == NULL, base < 2 or > 36
     char *original = str;
     if (value < 0) {
       *str++ = '-';
     } else {
       value = -value;
     }
     itoa_recursive_helper(value, str, base);
     return original;
   }
   

5. If you care about portability with ASCII and non-ASCII character sets and need to work in bases > 10, the following works well.

   *str++ = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[digit];