Итоа рекурсивно

Question

Я пытался написать рекурсивную версию функции itoa, код показан ниже.

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

Но код не идеален. Он использует static переменная и, вероятно, не выполняется так быстро, как должно быть. Я пытаюсь достичь алгоритма O(n). Кто-нибудь может показать мне лучший способ? Я также думаю, что статическая переменная не нужна, но я не совсем уверен, как этого избежать. Должен ли я разбить функцию на два порядка, чтобы избежать статической переменной?

Answer 1

Если вы хотите решить это рекурсивно, более простой подход - вернуть последний индекс:

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

Вы также можете решить это с помощью указателей:

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

Однако следует отметить, что эта реализация подвержена переполнению буфера. Вы должны быть уверены, что вы выделили достаточно большой буфер, чтобы вместить все целое представление ascii. Хорошей идеей было бы включить некоторые проверки границ.

Answer 2

Итоа должна вернуть пустоту.
Я не проверял это, но я верю, что это сработает.
Без статических переменных, без вспомогательных функций, без дополнительных аргументов.
Избыточное целочисленное деление в цикле while может быть слабым местом.

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

У вас также есть особенность, что itoa возвращает адрес конца строки.

Answer 4

Удивительное решение, хотя одна маленькая проблема. Этот код получает ошибку сегментации, потому что базовый случай рекурсии: когда n==0 не обрабатывается должным образом. Я сделал небольшое изменение в вашей программе, и теперь она работает нормально.

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

Теперь для моего собственного двух пенсов я решил это, не используя деление, а вместо этого используя двойные указатели для значений, которые сохраняются между вызовами функций.

Единственным недостатком моего решения является то, что нам нужно сохранить начальный адрес массива символов.

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