Convert string to integer recursively?

Question

Here is a simple function that converts a string to an integer.

int str2int(char *str)
{
    int ret = 0;
    char *c;

    for (c = str; (*c != '\0') && isdigit(*c); ++c)
        ret = ret*10 + *c - '0';

    return ret;
}

As an exercise, I'd like to write a recursive function that does the same thing. This is what I came up with.

int str2int2(char *c, int *i)
{
    if (*c == '\0' || !isdigit(*c))
        return *i;

    *i = *i * 10 + *c - '0';

    return str2int2(c + 1, i);
}

.
.
int i = 0;
.
... str2int2(str, &i);

Is there a way to write the recursive function without using the extra int* argument?

Answer 1

I think you may use horner scheme in order not to keep any 'i'.

You must reverse the string (yeah quit ugly) and then you can simply use:

int str2int (char* str)
{
    if (*str+1)
    {
     return 10*str2int(str+1)+(*str-'0');
    }
    return 0;
}

Answer 2

Well, you could hide the functionality from the person using the function. So you will have a function named int str2int(char *str) which will call int str2int(char *c, int *i) thereafter.

It's how I've done it in the past.

Answer 3

Sure, it's easy enough, but you need to write two functions, one with an accumulator, like this:

int str2int_rec(char *c, int accum)
{
    if (!c || !*c || !isdigit(*c))
        return accum;

    return str2int_rec(c + 1, accum * 10 + (*c - '0'));
}

int str2int(char *c)
{
    return str2int_rec(c, 0);
}

Answer 4

One way could involve passing the length of the digit as an argument so we can read backwards efficiently:

int strtoi(char *c, size_t l)
{
    return l ? c[l-1] - '0' + 10 * strtoi(c, l - 1) : 0;
}

Then call it like this:

int i = strtoi("432", 3);

Or:

char *c = "432";
int i = strtoi(c, strlen(c));

But it's not always optimal to bother with the length of a string. Plus, if a string has characters after a number, we'd have to factor that in manually, because this function won't do it for us. We can't (shouldn't) use strlen() inside our function to avoid having to pass arguments, because that can cause a considerable slowdown to recalculate the string's length every time. Surely there must be a way to do this from the beginning, even if we have to bring out the heavy artillery:

int strtoi(char *c)
{
    if(!isdigit(*c)) return 0;
    int i = strtoi(c + 1);
    return i + pow(10, (int)(log(i + 1)/log(10)) + (i != 0)) * (*c - '0');
}

And no, that (int) cast isn't optional. Basically, all of that math calculates the power of 10 we need to multiply our current digit by, based on the number returned by the last recursive call.

I understand this is probably a learning exercise, but recursion is not the be-all, end-all of programming. In some languages, and for some tasks, it is what some, myself included, would call beautiful, but from the looks of it this is not one of those cases.