Рекурсия - сумма из n натуральных чисел

#c #recursion #callstack #function-definition

#c #рекурсия #callstack #функция-определение

Вопрос:

функция для вычисления суммы из n натуральных чисел

 int solve(int n)
{
    if(n==0 or n==1)
    return n;
    int sum=0;

    sum=sum n;
    solve(n-1);   // gives me wrong output

    return sum;
}

int solve(int n)
{
    if(n==0 or n==1)
    return n;
    int sum=0;

    sum=sum solve(n-1);  // gives me correct output

    return sum;
}

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

1. Похоже, что solve возвращает что-то довольно важное, и игнорировать то, что оно возвращает, не совсем правильно, что ты думаешь?

2. Рекурсия использует стек для выполнения. В вашем первом решении вы выполняете только сумму первой итерации и снова вызываете функцию sum с уменьшенным значением, но не используете возвращаемое значение.

3. С помощью второй функции, solve(5) возвращенной 1 . Действительно ли это правильный вывод?

Ответ №1:

solve функция в первом методе не оказывает никакого эффекта в вашей программе

 int solve(int n)
{
    if(n==0 or n==1)
    return n;
    int sum=0;

    sum=sum n;
    solve(n-1);   // has not any effect

    return sum;
}

Во втором методе возвращаемое значение всегда будет равно 1, хотя оно должно возвращать сумму чисел, правильный код для вычисления суммы чисел является:

 int solve(int n)
{
    if (n == 0 || n == 1)
        return n;

    int sum = 0;

    sum = n   solve(n - 1);  // change 'sum' with 'n'

    return sum;
}

Выполнить:

solve(5);

Вывод:

5 4 3 2 1 = 15

Ответ №2:

В обеих функциях много общего.

Функции могут вызываться с отрицательным аргументом, потому что тип параметра — int. В этом случае вы можете получить бессмысленный результат.

Тип переменной, которая накапливает сумму чисел, должен быть больше, чем тип int, чтобы избежать переполнения.

Первая функция всегда возвращает значение переданного аргумента при первом рекурсивном вызове функции.

Это утверждение

 solve(n-1);   // gives me wrong output

не имеет эффекта, поскольку возвращаемое значение не используется.

Вторая функция всегда возвращает либо 0, либо 1 (при условии, что был передан неотрицательный аргумент) из-за этого оператора

 if(n==0 or n==1)
return n;

Потому что в этом фрагменте кода

 int sum=0;

sum=sum solve(n-1);  // gives me correct output

текущее значение аргумента не используется.

Кажется, здесь опечатка, и ее следует записать

 sum = n   solve(n-1);  // gives me correct output

Функция может быть объявлена и определена следующим образом, как показано в демонстрационной программе ниже.

 #include <iostream>

unsigned long long sum( unsigned int n )
{
    return n == 0 ? 0 : n   sum( n - 1 );
}

int main()
{
    std::cout << sum( 100 ) << 'n';
    
    return 0;
}

Результат программы является

Оператор return в функции также может быть записан как

 return n < 2 ? n : n   sum( n - 1 );

Чтобы уменьшить количество рекурсивных вызовов, функцию можно переписать следующим образом

 #include <iostream>

unsigned long long sum( unsigned int n )
{
    return n < 2 ? n : sum( n - 2 )   n   n - 1;
}

int main()
{
    std::cout << sum( 100 ) << 'n';
    
    return 0;
}