KR2 Exercise 4-12 - clc-wiki

The C Programming Language, 2nd Edition, by Kernighan and Ritchie
Exercise 4.12 on page 88

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.

Contents

1 Solution by Gregory Pietsch

2 Solution by Flash Gordon

3 Solution by Jesus Alvarez (Category 0)

4 Solution by menonsahab

5 Solution by gbar (Category 0)

6 Solution by Cromagnon (Category 0)

7 Solution by Oleksandr Melnykov (Category 0)

8 Solution by Codybartfast (cat 0)

9 Solution by anonymous

Solution by Gregory Pietsch

/* 

itoa() is non-standard, but defined on p.64 as having this prototype:

void itoa(int n, char s[])

Instead of this, I thought I'd use a different prototype (one I got from
the library manual of one of my compilers) since it includes all of the
above:

char *itoa(int value, char *digits, int base);

Description:  The itoa() function converts an integer value into an
ASCII string of digits.  The base argument specifies the number base for
the conversion.  The base must be a value in the range [2..36], where 2
is binary, 8 is octal, 10 is decimal, and 16 is hexadecimal.  The buffer
pointed to by digits must be large enough to hold the ASCII string of
digits plus a terminating null character.  The maximum amount of buffer
space used is the precision of an int in bits + 2 (one for the sign and
one for the terminating null). 

Returns:  digits, or NULL if error.

*/

#include <stdlib.h>

char *utoa(unsigned value, char *digits, int base)
{
    char *s, *p;

    s = "0123456789abcdefghijklmnopqrstuvwxyz"; /* don't care if s is in
                                                 * read-only memory
                                                 */
    if (base == 0)
        base = 10;
    if (digits == NULL || base < 2 || base > 36)
        return NULL;
    if (value < (unsigned) base) {
        digits[0] = s[value];
        digits[1] = '\0';
    } else {
        for (p = utoa(value / ((unsigned)base), digits, base);
             *p;
             p++);
        utoa( value % ((unsigned)base), p, base);
    }
    return digits;
}   

char *itoa(int value, char *digits, int base)
{
    char *d;
    unsigned u; /* assume unsigned is big enough to hold all the
                 * unsigned values -x could possibly be -- don't
                 * know how well this assumption holds on the
                 * DeathStation 9000, so beware of nasal demons
                 */

    d = digits;
    if (base == 0)
        base = 10;
    if (digits == NULL || base < 2 || base > 36)
        return NULL;
    if (value < 0) {
        *d++ = '-';
        u = -value;
    } else
        u = value;
    utoa(u, d, base);
    return digits;
}

Solution by Flash Gordon

Here is the first solution by Flash Gordon, which uses pointers which have not been introduced by this point. It relies on the C99 behaviour of dividing a negative number rounding towards zero.

char *itoa(int n, char s[], int base)
{
  int d = n % base;
  int r = n / base;
  if (n < 0) {
    *s++ = '-';
    d = -d;
    r = -r;
  }
  if (r)
    s = itoa(r, s, base);
  *s++ = "0123456789abcdefghijklmnopqrstuvwxyz"[d];
  *s = 0;
  return s;
}

Here is a solution not using pointers. It relies on the C99 behaviour of dividing a negative number rounding towards zero.

int real_itoa(int n, char s[], int base, int p)
{
  int d = n % base;
  int r = n / base;
  if (n < 0) {
    d = -d;
    r = -r;
  }
  if (r)
    p = real_itoa(r, s, base, p);
  s[p++] = "0123456789abcdefghijklmnopqrstuvwxyz"[d];
  return p;
}

void itoa(int n, char s[], int base)
{
  int p=0;
  if (n < 0)
    s[p++] = '-';
  s[real_itoa(n,s,base,p)] = 0;
}

Solution by Jesus Alvarez (Category 0)

#include <stdio.h>
#include <string.h>

#define MAX_STR 1000

void itoa(int, char [], int);
void reverse(char []);

int main()
{
        int ibuf = -12345;
        char istr[MAX_STR];
        istr[0] = '\0';
        printf("Integer: %d\n", ibuf);
        itoa(ibuf, istr, 0);
        printf("String: %s\n", istr);
        return 0;
}

void itoa(int num, char s[], int pos)
{
        int abs = 0;
        int buf = 0;

        if (num < 0) {
                num *= -1;
                abs = EOF;
        }
        buf = num % 10;
        if (buf > 0) {
                buf += '0';
                s[pos++] = buf;
                if ((num / 10) > 0) {
                        /* Reset the sign before recursion so that it is
                         * available in the tail of the recursion.*/
                        if (abs == EOF) {
                                num *= -1;
                        }
                        itoa(num /= 10, s, pos);
                } else {
                        if (abs == EOF) {
                                s[pos++] = '-';
                        }
                        s[pos] = '\0';
                }
        }
        if (pos == 1) {
                reverse(s);
        };
}

void
reverse (char s[])
{
        char c;
        int i, j;
        for (i = 0, j = strlen(s)-1; i < j; i++, j--){
                c = s[i];
                s[i] = s[j];
                s[j] = c;
        }
}

== Solution by Alex Hoang (Category 0) This solution relies on static variables to keep track of index and sign values as the program recurses through the levels. The main routine is used for testing.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXSTRING 1000

void my_itoa(int n, char s[])
{
    static int i;
    static int sign = 0;


    if (sign == 0)  /* Get sign only if this was a non-recursive call (called by a routine other than itself).*/
    {
        sign = (n < 0) ? -1 : 1;
        i = 0; /* Index is initialized only on non-recursive call. */
    }
    if (n / 10)
        my_itoa(n / 10, s);

    if (sign != 0)
    {
        if (sign < 0)
            s[i++] = '-';
        sign = 0; /* Reset the sign to get ready for next non-recursive call. */
    }

    s[i++] = abs(n % 10) + '0';
    s[i] = '\0';
}

main()

{
    int array[22] =
    {   0,
        1,
        2,
        9,
        10,
        11,
        16,
        17,
        21,
        312,
        -0,
        -1,
        -2,
        -9,
        -10,
        -11,
        -16,
        -17,
        -21,
        -312,
        INT_MAX,
        INT_MIN,
        };

    int i;
    char s[MAXSTRING];

    for (i = 0; i < 22; ++i)
    {
        my_itoa(array[i], s);
        printf("%d    %s\n", array[i], s);
    }


    return 0;
}

Solution by menonsahab

// Remark: It won't work for INT_MIN

#include <stdio.h>
#include <limits.h>
#define MAXLEN 100

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

int main()
{
	int n = INT_MIN + 1;
	char str[MAXLEN];
	itoa(n, str);
	printf("%s\n", str);
	return 0;
}

Solution by gbar (Category 0)

menonsahab's solution above won't work properly if called more than once in the same program. For example:

char * itoa(int n, char *s);
int main()
{
    char str[MAXLEN];
    itoa(10, str);
    itoa(-10, str);
    printf("%s\n", str);
    return 0;
}

Will print:

10-10

This solves that. I also changed the return type to void.

void itoa(int n, char s[])
{
    static int i = 0, calls = 0;
    calls++;
    
    if (n<0){
        s[i++] = '-';
        n = -n;
    }
    if (n/10){
        itoa(n/10, s);
    }
    
    s[i++] = n%10 + '0';
    s[i] = '\0';

    calls--;
    
    if (calls==0){
        i=0;
    }
}

Solution by Cromagnon (Category 0)

This solution does not use static variables. It uses regular argument and return values for communication between the levels of recursion.
One must call it with i equal to 0, such as itoa(-1337, s, 0), since non-zero values are used by the function itself: it uses i to indicate the position in the string it begins writing to, thus calling i = 0 writes from the beginning of the string. Each time it calls itself, it sets i to the position of the last character written into the string by the child call, so the father call writes after it.

/* itoa: convert n to characters in s; recursive version */
int itoa(int n, char s[], unsigned int i)
{
  if (n < 0) {
    s[i++] = '-';
    n = -n;
  }
  if (n / 10)
    i = itoa(n / 10, s, i++);
  s[i++] = n % 10 + '0';
  s[i] = '\0';
  return i;
}

Solution by Oleksandr Melnykov (Category 0)

This solution correctly works for INT_MIN.

#include <stdio.h>
#include <limits.h>

#define MAX_STR_LEN 1000

void itoa(int, char[]);
int _itoa(unsigned int, char[], int);

int main()
{
    char s[MAX_STR_LEN];

    itoa(12345, s);
    printf("%s\n", s); /* "12345" */

    itoa(-54321, s);
    printf("%s\n", s); /* "-54321" */

    itoa(0, s);
    printf("%s\n", s); /* "0" */

    itoa(INT_MAX, s);
    printf("%s\n", s); /* "2147483647" */

    itoa(INT_MIN, s);
    printf("%s\n", s); /* "-2147483648" */
}

/* converts integer n into string s */
void itoa(int n, char s[])
{
    unsigned int un;
    int i = 0;
    if (n < 0)
    {
        s[i++] = '-';
        un = -n;
    }
    else
    {
        un = n;
    }
    _itoa(un, s, i);
}

int _itoa(unsigned int n, char s[], int i)
{
    if (n >= 10)
        i = _itoa(n / 10, s, i);
    s[i++] = n % 10 + '0';
    s[i] = '\0';
    return i;
}

Solution by Codybartfast (cat 0)

Works for the largest negative number:

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

	if (n < 0)
		s[i++] = '-';
	else
		n = -n;
	s[itoar(n, s, i)] = '\0';
}

int itoar(int n, char s[], int i)
{
	if (n <= -10)
		i = itoar(n / 10, s, i);
	s[i++] = '0' - (n % 10);
	return i;
}

As n will have a negative value to be strictly C89 compliant should also need to deal with possibilty / and % might floor towards negative infiinty (where -3 / 10 = -1 and -3 % 10 = 7).

int adj = ((-3 / 10) == -1) ? 10 : 0;

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

	if (n < 0)
		s[i++] = '-';
	else
		n = -n;
	s[itoar(n, s, i)] = '\0';
}

int itoar(int n, char s[], int i)
{
	if (n <= -10)
		i = itoar(n / 10, s, i);
	s[i++] = '0' - ((n % 10) - adj);
	return i;
}

Solution by anonymous

This doesn't handle INT_MIN since that would require some ugly code or relying on a specific versions of C. This solution handles multiple calls to itoa and smartly terminates the string.

#include <stdio.h>

/*
    Exercise 4-12. 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.
*/

void itoa(int n, char s[]);

int main()
{
    int a = -2147483647, b = 1234567890;
    char s1[100], s2[100];
    itoa(a, s1);
    itoa(b, s2);
    printf("%d\n%s\n", a, s1);
    printf("%d\n%s\n", b, s2);
    return 0;
}

// convert n to characters in s
void itoa(int n, char s[])
{
    static int i = 0, num = 0; // static is so i and num are the same variable each time itoa is called instead of being initialized as a new ones
    num++; // keep track of number of recursive calls
    if (n < 0)
    {
        s[i++] = '-';
        n = -n; // this does not support the INT_MIN value
    }
    if (n / 10)
        itoa(n / 10, s);
    s[i++] = n % 10 + '0';
    num--;  // decrement number of recursive calls
    if (num == 0) // if all recursive calls have finished, terminate string and reset i
    {
        s[i] = '\0';
        i = 0;
    }
}

From clc-wiki

Contents

Solution by Gregory Pietsch

Solution by Flash Gordon

Solution by Jesus Alvarez (Category 0)

Solution by menonsahab

Solution by gbar (Category 0)

Solution by Cromagnon (Category 0)

Solution by Oleksandr Melnykov (Category 0)

Solution by Codybartfast (cat 0)

Solution by anonymous

Views

Personal tools

Site_logo

Search

Content_hierarchy

Tools