c - itoa 递归地

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 表示。一个好主意是包括一些边界检查。