K&R C Programs Exercise 4-12 - C Program Examples

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.

K&R’s printd (Section 4.10) prints a number recursively: recurse on n/10 to print all leading digits first, then putchar(n%10 + '0') on the way back up. itoa must do the same but write into a string instead of printing. The challenge: printd knows the correct position automatically (stack frame order), but itoa needs an explicit index into the output array. The cleanest solution uses a helper with a position parameter; the position increments as the recursion unwinds.

Solution

/* K&R Exercise 4-12 — recursive itoa
 * Compile: gcc -ansi -Wall ex4-12.c -o ex4-12 */
#include <stdio.h>
#include <string.h>

/* Helper: writes digit at s[*pos], increments *pos */
static void itoa_helper(int n, char s[], int *pos)
{
    if (n < 0) {
        s[(*pos)++] = '-';
        n = -n;
    }
    if (n / 10)                          /* recurse until single digit */
        itoa_helper(n / 10, s, pos);
    s[(*pos)++] = n % 10 + '0';
}

void itoa(int n, char s[])
{
    int pos = 0;
    if (n == 0) { s[pos++] = '0'; }     /* special case */
    else        { itoa_helper(n, s, &pos); }
    s[pos] = '\0';
}

int main(void)
{
    char buf[50];
    itoa(12345, buf);  printf("%s\n", buf);   /* 12345 */
    itoa(-999,  buf);  printf("%s\n", buf);   /* -999  */
    itoa(0,     buf);  printf("%s\n", buf);   /* 0     */
    itoa(1,     buf);  printf("%s\n", buf);   /* 1     */
    return 0;
}

How the Recursion Works

For n = 123:

itoa_helper(123, ...)    — recurses: itoa_helper(12, ...)
  itoa_helper(12, ...)   — recurses: itoa_helper(1, ...)
    itoa_helper(1, ...)  — 1/10 == 0, write '1', pos=1
  writes '2', pos=2
writes '3', pos=3

The stack frame ordering ensures digits appear left-to-right without any reversal step (contrast with K&R’s iterative itoa which must call reverse afterward).

Compile and Run

gcc -ansi -Wall ex4-12.c -o ex4-12
./ex4-12

Sample Output

What This Exercise Teaches

Recursion as implicit reversal — writing digits on the way back up from the recursive calls naturally produces left-to-right order; you get reversal for free from the call stack
INT_MIN edge case — -(-INT_MIN) overflows in C; production code needs unsigned arithmetic for the negative case; this exercise uses simple n = -n which is sufficient for the pedagogical goal
Static helper pattern — a public wrapper (itoa) with a clean interface hides the recursive helper that carries extra state

Set Up Your C Environment

← Exercise 4-11 |
Chapter 4 Solutions |
Exercise 4-13 →

Book: The C Programming Language, 2nd Ed — Kernighan & Ritchie