Wywołanie funkcji rekurencyjnej dla skróconego wektora

Question

Dobry wieczór. Mam za zadanie stworzyć program, który rekurencyjnie obliczy sumę liczb z wektora. Chciałem, aby funkcja zwracała ostatnią liczbę w wektorze i start tej samej funkcji na wektorze krótszym o 1 liczbę. Niestety program zwraca błąd: invalid use of void expression. Z góry dziękuję za pomoc w rozwiązaniu problemu.

#include <iostream>
#include <vector>

using namespace std;

int sumaWyrazow (vector<int>liczby) {
    if(liczby.size() == 1) {
        return liczby.back();
    }

    return liczby.back() + sumaWyrazow(liczby.pop_back());
}

int main() {
    vector<int>liczby{1,6,-2};

    cout <<sumaWyrazow(liczby);

    return 0;
}

 

Comments

Typ zwracany metody pop_back to void (choć technicznie rzecz biorąc to nie typ), a funkcja przyjmuje vector intów.

Answer 1

C++ nie ma tail/rest na wektorze można ją nieefektywnie zasymulować:

int sumaWyrazow (vector<int>liczby) {
    if(liczby.size() == 0) {
        return 0;
    }
    return liczby[0] + sumaWyrazow(std::vector<int>(liczby.begin() + 1, liczby.end()));
}

Lepiej byłoby przekazywać jeszcze indeks do funkcji, (złożoność się poprawi, liniowa, a nie jak powyższy kwadratowa):

int sumaWyrazow1(std::vector<int> liczby, int i) {
  if (i == liczby.size())
    return 0;
  return liczby[i] + sumaWyrazow1(liczby, i + 1);
}

 

Comments

Warto jeszcze pamiętać o tym,  aby pierwszy argument funkcji sumaWyrazow1 był przekazywany przez referencję, co w przypadku tego typu rekurencji ma kolosalne znaczenie w zmniejszeniu narzutu pamięciowego i czasowego.

int sumaWyrazow1( const std::vector<int>& liczby, int i)