Проблема реализации рекурсии. Задание в описании. Язык - С++

Question

Задание элементарное, но прошу не смеяться и не унижать.

Дана последовательность из N чисел Х1, Х2, … , ХN. Вычислить значение выражения: Хn(Хn+Xn-1)(Хn+Xn-1+Xn-2)(Хn+Xn-1+Xn2+Xn-3) ... (Хn+Xn-1+Xn-2+...+X1). Массив не использовать.

В случае моей программы, рекурсивная функция постоянно возвращает значение последнего введённого аргумента, в итоге, например, при вводe 3 программа выводит значение 3 умножить на 6 умножить на 9, а не 3 умножить на 5 умножить на 6. Как возможно это исправить? Код приведён.

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
static int sum = 0;
static int rez = 1;
int a;

int function(int nn)
{
    if (nn == 0)
        return 0;
    else if (nn > 0) {
        cin >> a;
        sum = function(nn - 1) + a;
        rez = rez * sum;
        return sum;
    }
}

int main()
{
    setlocale(LC_ALL, "RUS");

    int n;

    cout << "Введите количество цифр: " << endl;

    cin >> n;

    function(n);
    cout << rez;
}

Answer 1

Для решения задачи не нужны ни массивы ни рекурсия, достаточно одного цикла.

i := 3
sum := 0
res := 1
for ; i > 0; i-- {
    sum = sum + i
    res = res * sum
}

(ps. да простят меня за синтаксис, но под рукой был golang)

Answer 2

Вероятно, сложность представляет то, что суммирование ведётся в обратном порядке. Рекурсивная функция должна на каждом уровне иметь и сумму значений от последующего ввода, и произведение сумм последующих вводов. Для возврата пары параметров используем результат функции и ссылочную переменную (наверное, на текущем уровне обучения не стоит использовать возврат пары/тупля). Для того, чтобы при вызове из main не заводить переменную для суммирования, введём функцию-прокладку.

int func(int n, int &summ) {
    int x;
    cin >> x;

    if (n == 1)
        return summ = x; 

    int prod = func(n - 1, summ);
    summ += x;
    return summ * prod;
}

int f(int n) {
    int s = 0;
    return func(n, s);
}
int main()
{
    cout << f(3); 
}

Проверяем - для n=3 и ввода 5,2,3 получаем 150 = 3*(3+2)*(3+2+5)

P.S. Аналогичного результата можно добиться без рекурсии при использовании (явного) стека, но это может расцениваться как нарушение условия "Массив не использовать"

Answer 3

Задача была исправлена следующим кодом:

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;
static int rez = 1;

int function(int nn)
{   int a;
    int sum = 0;
    if (nn == 0)
        return 0;
    else if (nn > 0)
    {
        cin >> a;
        sum = a + function(nn - 1);
        rez = rez * sum;
        return sum;
    }
}

int main()
{
    setlocale(LC_ALL, "RUS");

    int n;

    cout << "Введите количество цифр: " << endl;

    cin >> n;

    function(n);
    cout << rez;
}

БЛОГ НА HUSL

Проблема реализации рекурсии. Задание в описании. Язык - С++

Ответы (3 шт):