Recursive itoa

[dgoodmaniii]

+AMDG

I'm having lots of trouble with K&R's Exercise 4-12, which
asks for a recursive version of itoa(n, s), which puts a
string version of integer n into string s. I had no trouble
doing this without recursion and the reversing it, but with
recursion I just can't figure it out.

Here's what I've got:

*******************
int itoa(int n, char s[])
{
static int i = 0;

if (n / 10) {
itoa(n / 10,s);
} else {
s[--i] = '\0';
i = 0;
}
if (n < 0 && i == 0) {
s[i++] = '-';
n = -n;
}
s[i++] = (n % 10 + '0');
return 0;
}
*******************

I'm testing it with the following for loops:
*******************
for (i=-11; i<=11; ++i) {
itoa(i,s);
printf("%s ",s);
}
putchar('\n');
for (i=11; i>=-11; --i) {
itoa(i,s);
printf("%s ",s);
}
putchar('\n');
*******************

It seems to work perfectly fine for positive numbers, and
for negative numbers of a single digit. After that, it
fails ingloriously, appropriately producing the negative
symbol and the first digit but spewing several digits of
garbage thereafter.

Can anyone help me out with this?

 

[Flash Gordon]

+AMDG

I'm having lots of trouble with K&R's Exercise 4-12, which
asks for a recursive version of itoa(n, s), which puts a
string version of integer n into string s. I had no trouble
doing this without recursion and the reversing it, but with
recursion I just can't figure it out.

Here's what I've got:

*******************
int itoa(int n, char s[])
{
static int i = 0;

First off, drop the static int. You are using it effectively to pass
information from a function (itoa) to the function which called it
(itoa) which is almost always the wrong thing to do. You use parameters
and return values to pass information! Note, of course, that you don't
have to pass the same value that you received for either parameter...
you can also return something other than 0...

if (n / 10) {
itoa(n / 10,s);
} else {

You always hit this at the deepest part of your recursion when you have
never changed i, so this will write before the beginning of the
string... also this is the only time you write a '\0' t terminate the
string...

s[--i] = '\0';
i = 0;
}
if (n < 0 && i == 0) {
s[i++] = '-';
n = -n;

Remember, changing a parameter does not change the value of the argument
in the calling function...

}

Will n always be positive here?

s[i++] = (n % 10 + '0');
return 0;
}
*******************

I'm testing it with the following for loops:
*******************
for (i=-11; i<=11; ++i) {
itoa(i,s);
printf("%s ",s);
}
putchar('\n');
for (i=11; i>=-11; --i) {
itoa(i,s);
printf("%s ",s);
}
putchar('\n');
*******************

It seems to work perfectly fine for positive numbers, and
for negative numbers of a single digit. After that, it
fails ingloriously, appropriately producing the negative
symbol and the first digit but spewing several digits of
garbage thereafter.

Can anyone help me out with this?

Well, it doesn't always work properly for positive numbers either, see
above. Also bad design using a static. Finally, and this is harder to
deal with... assuming a 16 bit processor (since the numbers are smaller
and easier to read than 32 or 64 bit...) you might well have the minimum
int value as -32768 and the maximum int value as +32767... so what will
happen if you negate -32768? As I say, for typical 32 and 64 bit
processors you have similar things, it's just the numbers are larger and
I can't remember them off the top of my head.

 

[Yoshi]

+AMDG

I'm having lots of trouble with K&R's Exercise 4-12, which
asks for a recursive version of itoa(n, s), which puts a
string version of integer n into string s.  I had no trouble
doing this without recursion and the reversing it, but with
recursion I just can't figure it out.

Here's what I've got:

*******************
int itoa(int n, char s[])
{
        static int i = 0;

        if (n / 10) {
                itoa(n / 10,s);
        } else {
                s[--i] = '\0';
                i = 0;
        }
        if (n < 0 && i == 0) {
                s[i++] = '-';
                n  = -n;
        }
        s[i++] = (n % 10 + '0');
        return 0;}

*******************

I'm testing it with the following for loops:
*******************
for (i=-11; i<=11; ++i) {
        itoa(i,s);
        printf("%s ",s);}

putchar('\n');
for (i=11; i>=-11; --i) {
        itoa(i,s);
        printf("%s ",s);}

putchar('\n');
*******************

It seems to work perfectly fine for positive numbers, and
for negative numbers of a single digit.  After that, it
fails ingloriously, appropriately producing the negative
symbol and the first digit but spewing several digits of
garbage thereafter.

Can anyone help me out with this?

Hi, how about following?


char* itoa(int n, char s[])
{

if(n < 0){
n = -n;
*s = '-';
s++;
}
if((n/10) == 0){
*s++ = n+'0';
*s = '\0';
}else{
s = itoa(n/10, s);
*s = (n%10) + '0';
*++s = '\0';
}
return s;
}

 

[Flash Gordon]

+AMDG

I'm having lots of trouble with K&R's Exercise 4-12, which
asks for a recursive version of itoa(n, s), which puts a
string version of integer n into string s. I had no trouble
doing this without recursion and the reversing it, but with
recursion I just can't figure it out.

Here's what I've got:

*******************
int itoa(int n, char s[])
{
static int i = 0;

if (n / 10) {
itoa(n / 10,s);
} else {
s[--i] = '\0';
i = 0;
}
if (n < 0 && i == 0) {
s[i++] = '-';
n = -n;
}
s[i++] = (n % 10 + '0');
return 0;}

*******************

I'm testing it with the following for loops:
*******************
for (i=-11; i<=11; ++i) {
itoa(i,s);
printf("%s ",s);}

putchar('\n');
for (i=11; i>=-11; --i) {
itoa(i,s);
printf("%s ",s);}

putchar('\n');
*******************

It seems to work perfectly fine for positive numbers, and
for negative numbers of a single digit. After that, it
fails ingloriously, appropriately producing the negative
symbol and the first digit but spewing several digits of
garbage thereafter.

Can anyone help me out with this?

Hi, how about following?


char* itoa(int n, char s[])
{

if(n < 0){
n = -n;
*s = '-';
s++;
}
if((n/10) == 0){
*s++ = n+'0';
*s = '\0';
}else{
s = itoa(n/10, s);
*s = (n%10) + '0';
*++s = '\0';
}
return s;
}

Now try passing INT_MIN to it, you will need to #include <limits.h>
You will find it does not work then... see my reply to the OP.
I do have a solution which works, but I would have to check C89 rules
for dividing negative integers and possibly tweak it a little...

 

[dgoodmaniii]

First off, drop the static int. You are using it effectively to pass
information from a function (itoa) to the function which called it
(itoa) which is almost always the wrong thing to do. You use parameters
and return values to pass information! Note, of course, that you don't
have to pass the same value that you received for either parameter...
you can also return something other than 0...

Well, I was trying to avoid having to pass the function a 0
every time when I started, but I rewrote it to include this
and to return the value of i, which seems to work correctly.
I also rewrote it to deal only with positive numbers for
now; see below.

You always hit this at the deepest part of your recursion when you have
never changed i, so this will write before the beginning of the
string... also this is the only time you write a '\0' t terminate the
string...

Yes, I see that you're right and that this is clearly
wrong...but how do I tell the function to write the '\0' to
terminate the string at the shallowest part of recursion?

Well, it doesn't always work properly for positive numbers
either, see above. Also bad design using a static.

Well, all I can say is that it *did* work for positive
numbers, all that I tested. And I'm aware it fails on the
largest (smallest?) negative number. Most of K&R's
conversion utilities do, and they don't seem concerned with
it because they're trying to teach general C concepts, which
is all I'm trying to learn. This exercise is trying to
teach recursion, not dealing with edge cases on data types.

Yoshi, thanks for the suggested solution, but I know just
enough C to know that it involves pointers, and that's
chapter 5. I'm on chapter 4, and haven't learned to deal
with pointers yet.

Thank you, Flash, for your suggestions. I'll let you all
know when I sort it out.

 

[dgoodmaniii]

+AMDG

Okay, feeling slightly dopey, I've figured out how to get
the string terminated; I just write '\0' as the last
character after every call, thereby ensuring that it will be
in the right place after the last one. (At least, it seems
to work, as of now.) I'm still working on the negatives,
though.

Thanks again.

 

[Flash Gordon]

Well, I was trying to avoid having to pass the function a 0
every time when I started,

There are other ways... one option involved using a helper function, as in..

int real_itoa(int n,char s[],int p)
{
...
}

void itoa(int n, char s[])
{
real_itoa(n,s,0);
}

This sort of thing is a common "trick". Sometimes the interface function
does a bit more work rather than just calling the real function,
sometimes not.

but I rewrote it to include this
and to return the value of i, which seems to work correctly.
I also rewrote it to deal only with positive numbers for
now; see below.

Dealing with positive numbers is easier than negative, and returning
your position is the key to avoiding the static.

Yes, I see that you're right and that this is clearly
wrong...but how do I tell the function to write the '\0' to
terminate the string at the shallowest part of recursion?

Well, it has to know when it is there (using the helper function method
I illustrate above solves that, since you have a non-recursive function
at the shallowest level), or you use the solution you suggest below.

Well, all I can say is that it *did* work for positive
numbers, all that I tested.

I was slightly disingenuous with my comment. Yes, I can understand that
you might get the expected result, bug because of the error you now
understand of writing to before the array *anything* could happen, and
in addition there was no guarantee that the array would be nul terminated.

And I'm aware it fails on the
largest (smallest?) negative number. Most of K&R's
conversion utilities do, and they don't seem concerned with
it because they're trying to teach general C concepts, which
is all I'm trying to learn. This exercise is trying to
teach recursion, not dealing with edge cases on data types.

Yes, that's fine. However, you might find it interesting and instructive
to try and think bout these things.

Yoshi, thanks for the suggested solution, but I know just
enough C to know that it involves pointers, and that's
chapter 5. I'm on chapter 4, and haven't learned to deal
with pointers yet.

I think this exercise is easier using pointers, and my initial solution
which I can show you if you want uses pointers. I've also adapted it to
use a helper and not use pointers.

My solutions do handle the maximum negative integer correctly ;-)

Thank you, Flash, for your suggestions. I'll let you all
know when I sort it out.

Always worth solving it yourself.

 

[dgoodmaniii]

+AMDG

Thanks to your help, I've gotten it working, and I'm pretty
satisifed with it by and large. Here's what I've got (no, I
haven't modified it to cover the largest negative integer,
though I might just because you brought it up):
***************
int itoa(int n, char s[], int i)
{
if (n < 0) {
s[i++] = '-';
n = -n;
}
if (n / 10) {
i = itoa(n / 10,s,i);
}
s[i++] = (n % 10 + '0');
s = '\0';
return i;
}
***************
The lessons learned here were also invaluable in solving
exercise 4-13 (a recursive function to reverse a string in
place).

That said, if I can ask a general question, what's the
*point* of recursion? K&R speak only generally, saying that
it often leads to more compact and easier to understand
code. That's certainly not true in this case, though; my
non-recursive code for itoa is only one line longer than
this, and that includes two local variables; plus the
function is simpler to use, requiring only two parameters
(the integer to be converted and the string to put it in).
Granted, it also requires reversal, but the reverse function
is easy, extremely compact (more so than the recursive
version I wrote for 4-13), and quick.

Further, I understood function calls to be rather expensive,
and the recursive version of these functions require more
function calls than the non-recursive ones, except when the
number is only one or two digits long. So wouldn't this not
only be harder to write, but also slower?

I did write a recursive function back in chapter one, for
breaking long input lines; I did so not knowing it was a
special feature not covered yet, and it made sense to me.
But in these cases, recursion just seems like an unnecessary
complication for no real benefit.

Is this just a factor of my inexperience? After four or
five more years, will I learn to love recursion?

 

[Seebs]

That said, if I can ask a general question, what's the
*point* of recursion?

It's often very expressive for problems which can be naturally decomposed
into similar, but smaller, problems.

People tend to use recursion for things like, say, expression parsers,
where an expression can have subexpressions which are basically the same
kind of thing -- the process of parsing is basically the same, just the
data change.

Sorting is another popular example. A lot of sorting operations consist of
"divide the list into two parts, sort each of them, then join them together".
But each part needs to be sorted, so you sort each part by dividing into
two parts... You get the idea.

It's not all that common, but it certainly does come up.

-s

 

[Eric Sosman]

It's often very expressive for problems which can be naturally decomposed
into similar, but smaller, problems.

People tend to use recursion for things like, say, expression parsers,
where an expression can have subexpressions which are basically the same
kind of thing -- the process of parsing is basically the same, just the
data change.

Sorting is another popular example. A lot of sorting operations consist of
"divide the list into two parts, sort each of them, then join them together".
But each part needs to be sorted, so you sort each part by dividing into
two parts... You get the idea.

It's not all that common, but it certainly does come up.

Some strategy games can be solved with recursive techniques.
"The current situation allows me three possible moves, leading
to situations A,B,C. What will my opponent do when confronted
with each of those situations?" You generate situations A,B,C
in turn, and call the what_should_I_do() function on each of
them, reversing the roles of player and opponent. Strategy
games are often simplified models of less formal real-world
problems, which may also be attacked similarly: "Starting from
Here, I could take any of streets A,B,C to try to get to There.
Street A would take me to the intersection of Highway X and
Byway Y, and then ..."

("Serious" search methods seldom rely on recursion alone,
but combine it with other techniques for greater efficiency.
For example, a purely recursive search *will* completely solve
the game of chess, but completing the search would challenge
most people's hardware budget and life expectancy.)

 

[Flash Gordon]

Some strategy games can be solved with recursive techniques.
"The current situation allows me three possible moves, leading
to situations A,B,C. What will my opponent do when confronted
with each of those situations?" You generate situations A,B,C
in turn, and call the what_should_I_do() function on each of
them, reversing the roles of player and opponent. Strategy
games are often simplified models of less formal real-world
problems, which may also be attacked similarly: "Starting from
Here, I could take any of streets A,B,C to try to get to There.
Street A would take me to the intersection of Highway X and
Byway Y, and then ..."

("Serious" search methods seldom rely on recursion alone,
but combine it with other techniques for greater efficiency.
For example, a purely recursive search *will* completely solve
the game of chess, but completing the search would challenge
most people's hardware budget and life expectancy.)

So much so that I don't think that anyone has ever done it.
In fact, you would need some other techniques as well to avoid infinite
loops, i.e. detecting when you have returned to an earlier position.

You also hit indirect recursion sometimes. I deal with this a fair bit
in code written by someone else. There is a general routine which you
call to display a windows and handle the user input. The user presses a
button which gets some code called from this which in turn throws up
another window be calling the function I first mentioned.

 

[Flash Gordon]

On Dec 19, 6:08 pm, (e-mail address removed) wrote:

+AMDG

I'm having lots of trouble with K&R's Exercise 4-12, which
asks for a recursive version of itoa(n, s), which puts a
string version of integer n into string s. I had no trouble
doing this without recursion and the reversing it, but with
recursion I just can't figure it out.

Here's what I've got:

*******************
int itoa(int n, char s[])
{
static int i = 0;

if (n / 10) {
itoa(n / 10,s);
} else {
s[--i] = '\0';
i = 0;
}
if (n < 0 && i == 0) {
s[i++] = '-';
n = -n;
}
s[i++] = (n % 10 + '0');
return 0;}

*******************

I'm testing it with the following for loops:
*******************
for (i=-11; i<=11; ++i) {
itoa(i,s);
printf("%s ",s);}

putchar('\n');
for (i=11; i>=-11; --i) {
itoa(i,s);
printf("%s ",s);}

putchar('\n');
*******************

It seems to work perfectly fine for positive numbers, and
for negative numbers of a single digit. After that, it
fails ingloriously, appropriately producing the negative
symbol and the first digit but spewing several digits of
garbage thereafter.

Can anyone help me out with this?


Hi, how about following?


char* itoa(int n, char s[])
{

if(n < 0){
n = -n;
*s = '-';
s++;
}
if((n/10) == 0){
*s++ = n+'0';
*s = '\0';
}else{
s = itoa(n/10, s);
*s = (n%10) + '0';
*++s = '\0';
}
return s;
}

Now try passing INT_MIN to it, you will need to #include <limits.h>
You will find it does not work then... see my reply to the OP.
I do have a solution which works, but I would have to check C89 rules
for dividing negative integers and possibly tweak it a little...

I have one that looks like this:


void itoa(int n, char *s)
{
if (0 > n) {
*s++ = '-';
*utoa_plus_one(-(n + 1), s) = '\0';
} else {
*utoa_plus_zero(n, s) = '\0';
}
}

Yes, that is one way of dealing with the special case (assuming the
obvious definitions of the functions). I'm sure there is a more elegant
solution, I've just not had the energy to think of it.

 

[Beej Jorgensen]

Some strategy games can be solved with recursive techniques.

For fun one night, I used this approach to write a Monte Carlo-based
Tic-Tac-Toe player. For the record, it always managed to probably play a
perfect game.

-Beej