Recursive Incrementer

Question

I'm writing a recursive function that takes a char array, which represents a number, and a pointer to a digit in that array. The point of the function is to increment the number just like the ++ operator. However, when I try it out on the number '819'. It doesn't increment it to '820' but instead changes it to '810' (it increments the last digit but doesn't do the recursion that I want). Can someone help me out with this? Thanks.

#include <stdio.h>

char* inc(char *num, char* p)
{   
    if( *p>='0' && *p<='8' )
    {
     *p++;
    }
    else if ( *p=='9' )
    {
     *p = '0';
     inc(num, --p);
    }

    return num;
}

main()
{
    char x[] = "819";

    printf("%s\n", inc(x, x+strlen(x)-1) ); //pass the number and a pointer to the last digit
}

Answer 1

Change *p++ to (*p)++ ; You want to increment the number contained in p.

   char* inc(char *num, char* p)
    {   
        if( *p>='0' && *p<='8' )
        {
            (*p)++;       //==> change
        }
        else if ( *p=='9' )
        {
            *p = '0';
            inc(num, --p);
        }

        return num;
    }

EDIT:

++ operator has higher precedence over * . Hence,

*p++ ==> *p then p++; // p's value before the increment.

Refer the precedence table here.

Answer 2

It's because *p++ retrieves the character then increments the pointer. You want (*p)++ which increments the character at that pointer:

#include <stdio.h>

char *inc (char *num, char* p) {
    if (*p >= '0' && *p <= '8') {
        (*p)++;
    } else if (*p == '9') {
        *p = '0';
        inc(num, --p);
    }
    return num;
}

You should be very careful on running this on strings above 9xxx since you'll have to ensure you've left room for the next digit up (pre-fill it with 0 if necessary). Otherwise add protection such as the wrap feature below:

#include <stdio.h>

char *inc (char *num, char* p) {
    if (p < num)
        return num;
    if ((*p < '0') || (*p > '9'))
        return num;
    if (*p < '9') {
        (*p)++;
        return num;
    }
    *p = '0';
    return inc(num, --p);
}

int main (int argc, char *argv[]) {
    char x[] = "819";
    char y[] = "8999";
    char z[] = "9999";
    char a[] = "aaa72";
    char b[] = "aaa279";
    char c[] = "aaa9999";
    printf("%s\n", inc(x, x+strlen(x)-1) );
    printf("%s\n", inc(y, y+strlen(y)-1) );
    printf("%s\n", inc(z, z+strlen(z)-1) );
    printf("%s\n", inc(a, a+strlen(a)-1) );
    printf("%s\n", inc(b, b+strlen(b)-1) );
    printf("%s\n", inc(c, c+strlen(c)-1) );
    return 0;
}

This code results in:

820
9000
0000
aaa73
aaa280
aaa0000

as expected.

Answer 3

I always follow some guidelines that help achieving correctness when coding in C++:

• Do not modify and get the value of anything in the same instruction. i.e. inc(num, --p); is banned because the second argument of inc is not const.
• Never dereference a pointer and do something with it in the same line. i.e. All forms of (*p)++; are banned.
• Always guarantee const-correctness in function parameters.
• Command/query separation: Functions should generally either be const or void.
• Do not use recursion if you can avoid it i.e. always look for a non-recursive alternative first. (This question is an example in which you can avoid it).
• Design by Contract. Add preconditions to the beginning, and postconditions to the end of your functions.

Applying them to your function may help to remove bugs in it.

Answer 4

An example of the side-effect of the original program as compiled on gcc, (This side-effect doesn't happen on @Pax program)

int
 main()
{
char x[] = "9";
char z[] = {57,57,57,57};

int t=0;
for(t=0;t<4;++t)
 printf("z == %d\n",z[t]);

inc(x, x+strlen(x)-1);

for(t=0;t<4;++t)
 printf("z == %d\n",z[t]);

}

output: z == 57 z == 57 z == 57 z == 57 z == 48 z == 48 z == 48 z == 48