itoa递归 [英] itoa recursively

问题描述

我一直想写一个递归功能 itoa 的版本，code如下图所示。

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

不过，code是不理想。它采用了静态变量，可能没有执行一样快，它应该是。我想实现的 O（N）算法。谁能给我一个更好的办法？我还认为，静态变量不是necesary，但我不是pretty知道如何避免它。我应该打破功能分为两个序，以避免静态变量？

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?

推荐答案

如果你想递归地解决它，更简单的方法可能是回到最后一个索引：

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

不过上要注意的是，这个实现很容易出现缓冲区溢出。你需要确定你分配一个足够大的缓冲，以适应整数的整个ASCII重新presentation。一个好的想法是包括一些边界检查。

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.

这篇关于itoa递归的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！