K&R 4-12 recursive converter int to string

Question

The exercise is:

Adapt the ideas of printd to write a recursive version of itoa; that is, convert an integer into a string by calling a recursive routine.

I wonder if I have correctly answered the question.

# include <stdio.h>
# define MAX 100
int itoa (char s[], int n)
{
 static int i = 0; 
 if (n < 0) {
 s[i++] = '-';
 n = -n;
 }
 if (n / 10)
 itoa (s, n / 10);
 if (i < MAX-1)
 s[i++] = n % 10 + '0';
 else {
 s[i] = '0円';
 return 0;
 }
 return 1;
}
int main ()
{
 int number = -123456789;
 char string[MAX] = { 0 };
 if (itoa(string, number))
 printf("The string is : %s\n", string);
 else
 printf("Error : array limit reached\n");
}

I presented it in a way it's not directly a converter but mostly. I'm a beginner so I don't know if I write some strange things. Could you please review my code?

• 200_success: @CoolGuy Code must be preserved verbatim, including whitespace.
• Spikatrix: @200_success , Ok. I removed those whitespace as they made those lines gray instead of having correct syntax highlighting

Answer 1

A static index in a recursive function is 1) used incorrectly 2) should be avoided.

The goal of a function is code re-use. OP's itoa() relies on static int i = 0;, which although good to initialize, only happens once. Subsequent uses of OP's itoa() would need to somehow need to do i = 0;

Even if code set i = 0; before each call to itoa(), code has trouble in a multiple thread environment, unless separate static copies of i are employed.

Conclusion: do not use a static i. There are better approaches.

---

n = -n; is a problem when INT_MIN == n (and int using typical 2's complement). As code wants to test the sign and then fold positive and negative numbers together, instead of folding them to positive numbers, fold then to negative numbers. Given C's 3 integer encoding options of 2's complement, 1's complement and sign magnitude, the number of negative numbers is at least the amount of positive ones.

---

Breaking the task into a wrapper function which calls the recursive one allows one-time test and house-keeping to be done in the wrapper, rather than the recursive one. Good recursion uses minimal parameter/variable space and exceptional values should be weeded out in other code. Since a direct call to the recursive function then may lack certain checks, make the helper recursive function static to keep its access controlled.

---

Minor: itoa() is more often implemented in this parameter order: itoa(int n, char *s)

---

Consider that good code should qualify buffer size with a size_t size parameter. Something like itoa(int n, char *s, size_t size). As this is a learning exercise - set that aside for later growth.

---

Rather then # define MAX 100, consider a right-sized value and a better name.

#define INT_SIZEMAX (CHAR_BIT*sizeof(int)*10/33 + 3)
// 
#define INT_SIZEMAX (CHAR_BIT*sizeof(int)/3 + 3)

---

// Return location of next char to write
static char *itoa_helper(char *s, int value) {
 if (value/10) {
 s = itoa_helper(s, value/10);
 }
 *s = '0' - value % 10;
 return s+1;
}
void itoa(int n, char *s) {
 if (n < 0) {
 *s++ = '-';
 } else {
 n = -n;
 }
 *itoa_helper(s, n) = '0円';
}
char buf[INT_SIZEMAX];
itoa(INT_MIN, buf);

• Mahé: Thank, very clever and clear, with pointer you have no problem with any "i" variable. But pointer are afterward in my book, so normally I don't know anything about them and I was trying to solve without. I will learn about 2's complement. ok for static function. But I don't understand why : (CHAR_BIT*siz[...]33 + 3) value of INT_SIZEMAX and the meaning (I understand its use here) of a "size_t parameter" (but this point is maybe for later?) too.
• chux: @Mahé Consider trying to print and int. Its size is N or CHAR_BIT*sizeof(int) as CHAR_BIT is the number of bits per char (usually 8). A decimal digit encodes log10(2) bits of information. 10/33 > log10(2). So "sign", digits, and null character need about CHAR_BIT*sizeof(int)*10/33 + 3
• Gauthier: +1, nice answer! Only my opinion: I dislike have non-bools in conditionals. I'd rather have if (value/10 > 0). It feels more natural to say "if 42 is greater than 0", rather than "if 42". I wonder about the division and modulo, too. I know you shouldn't optimize too early, but stdlib's div() computes division and remainder in one step, which is just as readable if not more. gcc -O3 gives shorter code with div() (235 lines of assembly instead of 309), and since I believe having the division also looks better, I see no reason why not using div().
• Gauthier: (I really don't know why gcc doesn't make the div optimization by itself...)
• Gauthier: Ah, the assembly line count is only 109 against 107 with -O2, and the div() case calls to stdlib's div.

Answer 2

No, this is not a correct solution. Since i is static, the function will fail the second time it is used.

It also fails to handle INT_MIN correctly, since -INT_MIN will overflow an int.

You should never omit the "optional" braces for if, else, for, and while blocks. By doing so, you are contributing to future coding accidents. See this recent Apple security vulnerability and this quote from the author of jQuery:

I really dis-liked having unnecessary braces. This... unfortunate... style preference plagued us for quite a while and caused all sorts of avoidable logic errors.

• Mahé: @MartinR I tried to fix the static problem and to correct the "not NUL-terminate the result string". This is the only solution I have found to manage the "i" variable : static and reset... I corrected with your braces style recommendation. Here's my update : gist.github.com/mtardy/c26563a972ca7991ce79 Maybe it's a bit complicated and not very elegant but recursive routines are very complicated to me because of the management and definition of variables. I know it don't manage too big numbers' overflow anymore. Is that answer the question now?

Answer 3

Your function expects that the passed string buffer has space for MAX characters. A better design is to pass the buffer size as an additional parameter:

int itoa (char s[], size_t bufferSize, int n)

which is then used as

if (itoa(string, sizeof(string), number)) 

and makes the preprocessor definition MAX obsolete.

Also note that your function does not NUL-terminate the result string, the line

 s[i] = '0円';

is never executed unless the passed buffer is too small.