K&R exercise 4-12

[Tyler Smith]

Hi,

I'm working through K & R, and I have a few questions about recursive
functions. I've solved the problem at hand, but my solution seems
clumsy. In particular, I suspect there must be a better way to allow
link each instance of the function to the array cell that it produces.
I've used a static variable, which is ok except that it requires an
extra variable to indicate whether or not the function call was the
original, or spawned by another instance of printd.

Also, I've written this as a void function - since it's directly
modifying the string, is there any value to returning the string, or
is it fine to allow the calling program to simply access the modified
string?

I hope this makes sense. The code is pasted below.

Thanks,

Tyler

#include <stdio.h>

void printd (int n, char s[], int new)
{
static int p;
p = new ? 0: p;

if (n< 0 ) {
s[p++]='-';
n = -n;
}
if (n/10)
printd(n/10, s, 0);
s[p++]= (n % 10 + '0');
}

int main (void)
{
char s[100];

printd(123, s, 1);
printf("string is %s\n", s);

printd(456, s, 1);
printf("string is %s\n", s);
}

 

[Flash Gordon]

Tyler Smith wrote, On 09/08/07 18:41:

Hi,

I'm working through K & R, and I have a few questions about recursive
functions. I've solved the problem at hand, but my solution seems
clumsy. In particular, I suspect there must be a better way to allow
link each instance of the function to the array cell that it produces.

Yes, there is. See
http://clc-wiki.net/wiki/K&R2_solutions:Chapter_4:Exercise_12 for one
possible example.

I've used a static variable, which is ok except that it requires an
extra variable to indicate whether or not the function call was the
original, or spawned by another instance of printd.

Why did you not just pass s+1 in your recursive call? Remember, that the
parameter s is actually a pointer, not an array. I suggest having a look
at chapter 6 of the comp.lang.c FAQ located at http://c-faq.com

Also, I've written this as a void function - since it's directly
modifying the string, is there any value to returning the string, or
is it fine to allow the calling program to simply access the modified
string?

In C strings are not first class citizens, so this is actually quite normal.

I hope this makes sense. The code is pasted below.

Thanks,

Tyler

#include <stdio.h>

void printd (int n, char s[], int new)
{
static int p;
p = new ? 0: p;

if (n< 0 ) {
s[p++]='-';
n = -n;

This is a problem if n is the maximum negative value of an int on most
systems. For example on a typical 16 bit system the range of int is
-32768 to +32767, since 32768 is not in this range you should see the
problem. This may be why Gregory did things the way he did on his
attempt at the link I included.

}
if (n/10)
printd(n/10, s, 0);
s[p++]= (n % 10 + '0');
}

int main (void)
{
char s[100];

printd(123, s, 1);
printf("string is %s\n", s);

printd(456, s, 1);
printf("string is %s\n", s);

main returns an int, so returning one would be a good idea. 0 means
success so is a good value to choose.
return 0;

 

[Tyler Smith]

Why did you not just pass s+1 in your recursive call? Remember, that the
parameter s is actually a pointer, not an array. I suggest having a look
at chapter 6 of the comp.lang.c FAQ located at http://c-faq.com

The problem is that the last call to the function produces the first
number in the string. So passing s+1 produces the string in reverse
order. Which gives me some clues about the solution for question 4-13,
but I'll have to work some more to use this with the current problem.

Thanks,

Tyler

 

[pete]

The problem is that the last call to the function produces the first
number in the string. So passing s+1 produces the string in reverse
order. Which gives me some clues about the solution for question 4-13,
but I'll have to work some more to use this with the current problem.

void itoa(int n, char *s);
static char *utoa(unsigned n, char *s);
static char *utoap1(unsigned n, char *s);

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

static char *utoa(unsigned n, char *s)
{
unsigned digit, tenth;

tenth = n / 10;
digit = n - 10 * tenth;
if (tenth != 0) {
s = utoa(tenth, s);
}
*s = (char)(digit + '0');
return s + 1;
}

static char *utoap1(unsigned n, char *s)
{
unsigned digit, tenth;

tenth = n / 10;
digit = n - 10 * tenth;
if (digit == 9) {
if (tenth != 0) {
s = utoap1(tenth, s);
} else {
*s++ = '1';
}
*s = '0';
} else {
if (tenth != 0) {
s = utoa(tenth, s);
}
*s = (char)(digit + '1');
}
return s + 1;
}

 

[Tyler Smith]

recursive itoa function.

Thanks! It took me twenty minutes to walk myself through the code,
but now it looks so simple! How much time does one spend working on C
code until these sorts of solutions are obvious *before* you've been
shown them I wonder?

Cheers,

Tyler

 

[pete]

recursive itoa function.

Thanks! It took me twenty minutes to walk myself through the code,
but now it looks so simple! How much time does one spend working on C
code until these sorts of solutions are obvious *before* you've been
shown them I wonder?

At least five years for myself.