Thread: recursive itoa

You should be able to avoid the recursion if you just incremented 's' instead of indexing it.

Sure, if you use helper functions. Here's an example. I'm afraid it's not very nicely coded.

Code:

#include <stdio.h>

int my_itoa_r(int n, char *s, int digit) {
    int d, max;
    
    if(n == 0) {
        s[digit] = 0;
        return digit;
    }
    
    d = n % 10;
    max = my_itoa_r(n / 10, s, digit + 1);
    s[max - digit - 1] = d + '0';
    
    return max;
}

void my_itoa(int n, char *s) {
    my_itoa_r(n, s, 0);
}

int main() {
    char buffer[BUFSIZ];
    int number = 123456;
    
    my_itoa(number, buffer);
    printf("itoa(%d) = \"%s\"\n", number, buffer);
    
    return 0;
}

Code:

int myitoa( char *s )
{
    if( s && *s && isdigit(*s) )
    {
        int n = *s - '0', l = 1, r = myitoa( s + 1 );
        while( r / l ) l *= 10;
        return n * l + r;
    }
    return 0;
}

You can add support for sign checking, but there's the general idea.


Quzah.

Slightly nicer version. Maybe not as nice as quzah's, but at least this is O(n).

Code:

#include <stdio.h>

void my_itoa_r(int n, char **s) {
    if(n == 0) return;
    
    my_itoa_r(n / 10, s);
    **s = n % 10 + '0';
    (*s) ++;
}

void my_itoa(int n, char *s) {
    my_itoa_r(n, &s);
    *s = 0;
}

int main() {
    char buffer[BUFSIZ];
    int number = 123456;
    
    my_itoa(number, buffer);
    printf("itoa(%d) = \"%s\"\n", number, buffer);
    
    return 0;
}

Originally Posted by Tool

Yes. But thats an exercise in K&R that explicitly says to write it recursively.

So, is there a way to write a recursive version without the static?

Oops, I meant to say "static" instead of "recursion". Oh well, there are plenty of examples from others.

I got mine backwards. Mine is atoi. Sorry, was on the phone.

Quzah.

Communicating back through a double-pointer is kind of cheating IMHO, because it's not possible in most functional languages where you would actually write recursive routines like this.

Code:

char *itoa( int n, char *s )
{
	if( n == 0 ) return s;
	*( s = itoa( n / 10, s ) ) = n % 10 + '0';
	return s + 1;
}

void itoa_wrapper( int n, char *s )
{
	if( n == 0 ) strcpy( s, "0" );
        else if( n < 0 ) { *s = '-'; itoa_wrapper( -n, s + 1 ); }
	else *itoa( n, s ) = 0;
}

edited to handle negatives

@quzah: Strangely, I too started writing an atoi() before I realized my mistake.

quzah's idea can, of course, be used to write an itoa() as well. It's just really inefficient. (Of course, since we're writing this recursively, we're probably not too concerned about efficiency . . . .)

I like brewbuck's solution best. Reading it made me realize that you need a helper function, though, because otherwise you can't know to turn 0 into "0" and not "", as far as I can tell.