Cześć, mam zadanie napisać naiwny algorytm rekurencyjny i iteracyjny rozwiązujący problem plecakowy. Jest to wersja gdzie mamy zadaną wagę n, oraz k elementów, gdzie zarówno n, jak i każdy element są dodatnie. Mój algorytm iteracyjny wykorzystuje stos i działa bez zarzutów, wersja rekurencyjna wykorzystuje listę wiązaną, musiałem napisać ją sam. No ale w każdym razie dochodzi do dziwnego błędu. Dla danych większych od 15 elementów dostaje przepełnienie stosu, dziwi mnie to, ponieważ jest to rekurencja ogonowa. Algorytm iteracyjny radzi sobie świetnie nawet z bardzo dużymi danymi. Bardzo łatwo było przepisać algorytm iteracyjny na rekurencyjny, ale to też powodowało ten sam błąd. Może mi ktoś powiedzieć gdzie tkwi problem? Poniżej zamieszczam fragment kodu. Dodam, ze funkcję wywołuję z argumentem <sumaOczekiwana - weights[0]> oraz listą z jednym elementem już na niej umieszczonym, tj indeksem 0, oraz dla tych danych dla których działa, zwraca poprawny wynik.
public static void plecak_rec(int[] weights, int S , Vector v){
//Jesli oczekiwana suma odjac suma elementow jest rowna 0,
//to oznacza ze znalezlismy rozwiazanie
if(S == 0)
return;
//Zatem teraz jestesmy w sytuacji, gdy suma elementow nie daje
//oczekiwanej sumy.
int last = v.getLast();
//Indeksy na liscie sa ulozone leksykograficznie, zatem jesli
//ostatni element jest najwiekszym mozliwym to tak czy inaczej
//go zdejmujemy.
if(last + 1 == weights.length){
v.popLast();
//Jesli po zdjeciu indeksu lista jest pusta to juz nie da
//sie rozpatrzec innych przypadkow. Brak rozwiazan.
if(v.isEmpty())
return;
S += weights[last];
//W przeciwnym przypadku aktualny ostatni indeks zwiekszamy
//o 1, oraz odopowiednio modyfikujemy sume
last = v.popLast();
S += weights[last];
v.pushBack(last+1);
S -= weights[last+1];
} else if(S < 0){
//W tym przypadku wiemy ze suma elementow jest troche za
//duza, oraz ostatni indeks na liscie nie jest maksymalny.
//Zdejmujemy go z listy i wrzucamy o 1 wiekszy na koniec
v.popLast();
S += weights[last];
v.pushBack(last+1);
S -= weights[last+1];
} else {
//Teraz wiemy, ze suma elementow jest wciaz za mala, oraz
//mozemy wziac indeks wiekszy od statniego. Dorzucamy
//zatem indeks wiekszy o 1 od ostatniego
v.pushBack(last+1);
S -= weights[last+1];
}
//Po tych modyfikacjach wywolujemy rekurencyjnie z nowymi danymi
//Mamy pewnosc ze dojdziemy do przypadku podstawowego, bo w
//kazdym wywolaniu modyfikujemy dane, zachowujac przy tym
//porzadek leksykograficzny. Latwo oszacowac maksymalna liczbe
//wywolan.
plecak_rec(weights, S, v);
}
Java 