itoa recursively

Question

I have been trying to write a recursive version of function itoa, the code is shown below.

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 the code is not ideal. It uses a static variable and probably is not executing as fast as it should be. I am trying to achieve a O(n) algorithm. Could anyone show me a better way? I also think that static variable is not necesary, but I'm not pretty sure how to avoid it. Should I break the function into two inorder to avoid the static variable?

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

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';  
}  

Answer 3

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 4

Amazing solution though one small problem. This code receives segmentation fault because the base case of recursion : when n==0 isn't handled properly. I made a small change to your program and now it works fine.

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

Now for my own two-pence, I solved this without using division but instead using double pointers for the values to persist between function calls.

Only demerit of my solution is that we need to preserve the starting address of the character array.

void itoa(char**a,int i)
{
    int dig;
    if(i<10) //base case;
    {
        **a=i+48;
        *(++(*a))='\0';
        return;
    }
    dig=i%10;
    itoa(a,i/10);
    **a=dig+48;  //char value + 48 will give me the corresponding value
    *(++(*a))='\0';
    return;
}

int main()
{
    char* t=(char*)malloc(sizeof(char)*5);
    char* save=t;
    int ti=1234;
    itoa(&t,ti);
    printf("%s",save);
}