Каков будет базовый случай рекурсивной функции, которая должна найти сумму чисел в строке

Question

Например, int num (char [100]) - это функция, которая находит сумму чисел в строке.

Например, "123omaewamou7" должно вернуть 130 .

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

Мое первое предположение состоит в том, что я проверю каждый символ строки, как я это делал в итеративном случае.

Какой совет вы могли бы дать, чтобы найти базовый вариант?

Answer 1

Вы можете использовать sscanf. Я считаю, что l oop будет лучше, но вот рекурсивная версия.

#include <stdio.h>

int calculateSum(char *string, int sum) {
    if (*string == '\0') return sum;

    int len = 0;
    int value = 0;

    if (sscanf(string, "%d%n", &value, &len) == 1) {
        sum += value;
    } else {
        len = 1;
    }

    string += len;

    return calculateSum(string, sum);
}

int main() {
    printf("%d\n", calculateSum("123omaewamou7", 0));
}

Answer 2

Базовым регистром рекурсивной функции является условие *s == '\0', где s - строка, переданная функции. То есть, когда встречается завершающий ноль строки.

Достаточно объявить только один параметр функции типа const char *. И тип возвращаемого значения должен быть long long int. Это снижает риск переполнения.

Функция может быть основана на использовании стандартной C функции strtoll.

Вот демонстрационная программа.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

long long int sum( const char *s )
{
    long long int value = 0;

    if ( *s )
    {
        if ( isdigit( ( unsigned char )*s ) || *s == '+' || *s == '-' )
        {
            char *p;

            value = ( strtoll( s, &p, 10 ) );

            s = p;
        }
        else
        {
            ++s;
        }

        value += sum( s );
    }

    return value;
}

int main(void) 
{
    const char *s = "123omaewamou7";

    printf( "sum = %lld\n", sum( s ) );

    return 0;
}

Вывод программы

sum = 130

Вы можете исключить, используя стандартную C функцию isdigit (и соответственно заголовок <ctype.h>), следующим образом

long long int sum( const char *s )
{
    long long int value = 0;

    if ( *s )
    {
        if ( ( '0' <= *s && *s <= '9' ) || *s == '+' || *s == '-' )
        {
            char *p;

            value = ( strtoll( s, &p, 10 ) );

            s = p;
        }
        else
        {
            ++s;
        }

        value += sum( s );
    }

    return value;
}

Answer 3

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