Write a recursive function in C that converts a number into a string

Question

I'm studying software engineering, and came across this exercise: it asks to write a recursive function in C language that receives a positive integer and an empty string, and "translates" the number into a string. Meaning that after calling the function, the string we sent would contain the number but as a string of its digits.

I wrote this function, but when I tried printing the string, it did print the number I sent, but in reverse.

This is the function:

void strnum(int n, char *str)
{
    if(n)
    {
        strnum(n/10, str+1);
        *str = n%10 + '0';
    }
}

For example, I sent the number 123 on function call, and the output was 321 instead of 123.

I also tried exchanging the two lines within the if statement, and it still does the same. I can't figure out what I did wrong. Can someone help please?

NOTE: Use of while and for loop statements is not allowed for the exercise.

Because `*str = n%10 + '0';` occurs *after your recursive call*, your digits will come out backwards. Mentally trace out the code execution, and you will see it. — Robert Harvey, Jun 11 '14 at 19:21
@RobertHarvey I think in this case, it will come out reversed regardless where the recursive call is. The first call (the first level of recursion that is) will always print the 3 — fjc, Jun 11 '14 at 19:23
the function needs to be modified such that the value is placed into the string after exiting all later recursions, with the final recursion level placing the first char into the string. I.E. the 'str' should be incremented just before exiting the recursion, not as part of the call to the next recursion. — user3629249, Jun 11 '14 at 21:07

score 4 · Answer 1 · edited Jun 20 '20 at 09:12

^{Note: your current implementation design is somewhat dangerous since you have no way of knowing if you are really writing in valid memory; consider implementing the function with a passed in len to know when you shouldn't try to write anymore; ie. to prevent buffer overruns.}

Introduction

The problem is that you are shaving off the least significant digit, but assigning it to the most significant position in the buffer pointed to by str.

You will need to have the "off shaving" and the "assigning" synchronized, so that the least significant digit is stored at the end - and not the beginning.

Hints

Easiest solution would be to do what you currently are doing, and then later reverse the buffer, but this will require far more assignments than what is actually required.

The recommended way is to calculate the number of digits in your string, by doing this you'll know at what offset the end will be, and start assigning the least significant digit at that position.

How do I determine the number of digits of an integer in C?

The hack

Another alternative is having the recursive call modify the current value of our pointer, effectively making it assign the right value - at the right offset.

This example is mostly included because it's "fun", there are (as mentioned) other paths to walk.

#include <stdio.h>

void strnum_impl (int n, char ** str) {
  if (n) {
    strnum_impl (n/10, str);
    **str = n%10 + '0';
    (*str)++;
  }
}

void strnum (int n, char * str) {
  if (n == 0)  {          *str++ = '0'; }
  else         { strnum_impl (n, &str); }

  *str = '\0'; /* null-terminate */
}

int main () {
  char buf[256];

  strnum (10240123, buf);
  printf (">%s<\n", buf);

  return 0;
}

>10240123<

might it be possible to shave off the most significant bit, and thereby avoid the reversing operation? — Michael Dorst, Jun 11 '14 at 19:25
@anthropomorphic mathematically shaving off the most significant bit is much harder, and an implementation in *C* would probably have to add another loop that runs until we only have one digit left in `n` (meaning; the most significant). — Filip Roséen - refp, Jun 11 '14 at 19:45

score 0 · Answer 2 · answered Jun 12 '14 at 19:25

As @Robert Harvey commented, as well as others, code is determining the least rather than the most significant digit and placing it in str[0].

It did look like fun to implement, so the below well copes with the entire range of int including INT_MIN and arbitrary sized int.

static char *strnum_helper(int n, char *str) {
  str[0] = '0' - n%10;
  if (n < -9) {
    return strnum_helper(n/10, str - 1);
  }
  return str;
}

void strnum(int n, char *str) {
  char buf[(sizeof n * CHAR_BIT)/3 + 3];  // Sized to any size int
  if (n < 0) {
    *str++ = '-';
    }
  else {
    n = -n; // By using negative numbers, do not attempt -INT_MIN
  }
  buf[sizeof buf - 1] = '\0';
  strcpy(str, strnum_helper(n, &buf[sizeof buf - 2]));
}

@Filip Roséen - refp pointed out the value of passing in a size. The above strnum() could be adjusted per a size limitation.

Write a recursive function in C that converts a number into a string

2 Answers2

Introduction

Hints

The hack