c - 什么是递归函数的基本情况，它应该在字符串中找到数字的总和

Question

例如，int num(char [100])是一个查找字符串中数字总和的函数。

例如 "123omaewamou7" 应该返回130。

我试图迭代地做它，似乎我已经掌握了它。但我也很好奇如何递归地做到这一点。虽然我什至没有想出递归函数的基本案例。

我的第一个假设是我将像在迭代案例中那样检查字符串的每个字符。

你能给出什么提示来找到基本案例？

Answer 1

你可以检查左边的字符串，我的意思是，如果你在基本情况下只有数字，你只需返回那个数字。

Answer 2

您可以使用 sscanf。我相信循环会更好，但这里是递归版本。

#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 3

递归函数的基本情况是*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（以及相应的 header <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;
}