Преобразовать строку в целое число рекурсивно?

Question

Вот простая функция, которая преобразует строку в целое число.

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

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

    return ret;
}

В качестве упражнения я хотел бы написать рекурсивную функцию, которая делает то же самое. Это то, что я придумал.

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);

Есть ли способ написать рекурсивную функцию без использования дополнительного аргумента int*?

Answer 1

Конечно, это достаточно просто, но вам нужно написать две функции, одна с аккумулятором, например:

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 2

Ну, вы можете скрыть функциональность от человека, использующего функцию. Таким образом, у вас будет функция с именем int str2int(char *str), которая после этого вызовет int str2int(char *c, int *i).

Это то, как я делал это в прошлом.

Answer 3

Один из способов может включать передачу длины цифры в качестве аргумента, чтобы мы могли эффективно читать в обратном направлении:

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

Тогда назовите это так:

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

Или:

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

Но не всегда оптимально беспокоиться о длине строки. Кроме того, если строка содержит символы после числа, мы должны были бы учесть это вручную, потому что эта функция не сделает это за нас. Мы не можем (не должны) использовать strlen() внутри нашей функции, чтобы избежать необходимости передавать аргументы, потому что это может привести к значительному замедлению, чтобы каждый раз пересчитывать длину строки. Наверняка должен быть способ сделать это с самого начала, даже если мы должны вывести тяжелую артиллерию:

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');
}

И нет, это (int) приведение не является обязательным. По сути, вся эта математика вычисляет степень 10, на которую мы должны умножить нашу текущую цифру, на основе числа, возвращенного последним рекурсивным вызовом.

Я понимаю, что это, вероятно, учебное упражнение, но рекурсия - это не главное, а конец всего программирования. На некоторых языках и для некоторых задач это то, что некоторые, в том числе и я, назвали бы красивым, но, судя по всему, это не один из таких случаев.

Answer 4

Я думаю, что вы можете использовать схему Хорнера , чтобы не оставить «я».

Вы должны перевернуть строку (да, отвратительно), и тогда вы можете просто использовать:

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