itoa recursively

Question

Ok, well i have been trying to write a recursive version of itoa, this is what i came up with.

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

     if(n / 10 != 0)
         itoa(n/10, s);
     else if(n < 0)
         i = 1; /* s[0] is allready taken by - sign */
     else 
         i = 0; /* reset i to 0 */

     if(n < 0) {
          s[0] = '-';
     }

     s[i++] = abs(n % 10) + '0';
     s[i] = '\0';
}

But i dont think its so good, it uses a static variable and probably isnt as fast as it should be - O(n), what i want to achieve. Could anyone show me a better way, and i also think that static variable isnt neccesary, but im not preety sure how to avoid it... if i want to avoid static ill need to break it into 2 functions then?

Answer 1

If you want to solve it recursively, an easier approach might be to return the last index:

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

    if(n / 10 != 0)
        i = itoa(n/10, s);
    else if(n < 0)
        s[i++] = '-';

    s[i++] = abs(n % 10) + '0';
    s[i] = '\0';

    return i;
}

You could also solve it using pointers:

char * itoa(int n, char * s)
{
    char * dest = s;

    if(n / 10 != 0)
        dest = itoa(n/10, dest);
    else if(n < 0)
        *dest++ = '-';

    *dest++ = abs(n % 10) + '0';
    *dest = '\0';

    return dest;
}

However on thing to note is that this implementation is prone to buffer overflows. You need to be certain that you have allocated a sufficiently large buffer to fit the entire ascii representation of the integer. A good idea would be to include some boundary checking.

Answer 2

char* itoa(int n, char s[]) {
  if (n < 0) {
    s[0] = '-';
    return itoa(-n, s+1);
  }
  if (n/10 > 0) {
     s = itoa(n/10, s);
  }
  s[0] = '0' + (n%10);
  s[1] = '\0';
  return &s[1];
}

You also have the feature that itoa returns the address of the end of the string.

Answer 3

itoa should return void.
I haven't tested this, but I believe it will work.
No static variables, no helper functions, no extra arguments.
The redundant integer division in the while loop may be a weakness.

void itoa(int n, char *s)  
{  
    char c;  
    if (n < 0)  
    {  
        *s++ = '-';  
        itoa(-n, s);  
        return;  
    }  
    c = '0' + n % 10;  
    itoa(n / 10, s);  
    while ( n /= 10 ) s++;  
    *s++ = c;  
    *s = '\0';  
}