itoa de forma recursiva

Question

He estado tratando de escribir una recursiva versión de itoa función, el código se muestra a continuación.

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

Sin embargo, el código no es lo ideal. Se utiliza una variable static y probablemente no se está ejecutando tan rápido como debería ser. Estoy tratando de lograr un O (n) algoritmo. ¿Alguien podría mostrar una mejor manera? También creo que la variable estática no es NECESARIO, pero no estoy bastante seguro de cómo evitarlo. Debería romper la función en dos finde para evitar la variable estática?

Answer 1

Si se quiere resolver de forma recursiva, un enfoque más sencillo podría ser la de devolver el último índice:

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

También puede resolverlo el uso de punteros:

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

Sin embargo, en que hay que señalar es que esta aplicación es propenso a desbordamientos de búfer. Usted necesita estar seguro de que usted ha asignado un buffer lo suficientemente grande para que quepa toda la representación ASCII del número entero. Una buena idea sería incluir algunas comprobaciones de límites.

Answer 2

itoa debería volverá vacía.
No he probado esto, pero creo que va a funcionar.
No hay variables estáticas, no hay funciones de ayuda, no hay argumentos adicionales.
La división de enteros redundante en el bucle, mientras que puede ser una debilidad.

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

También tiene la característica de que itoa devuelve la dirección de la final de la cadena.

Answer 4

solución increíble, aunque hay un pequeño problema. Este código de error de segmentación recibe debido a que el caso base de la repetición: cuando n==0 no se maneja correctamente. Hice un pequeño cambio en su programa y ahora funciona bien.

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

En cuanto a mi propia dos peniques, he resuelto esto sin usar división, pero en cambio el uso de punteros dobles para los valores que se mantengan entre las llamadas a funciones.

Sólo demérito de mi solución es que necesitamos para preservar la dirección inicial de la matriz de caracteres.

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