Optymalizacja rekurencji

Witam, stworzyłem prosty program rekurencyjny, który mimo iż działa dobrze i zwraca odpowiednie wyniki jest niepoprawny. Jak można zoptymalizować rekurencję przy pomocy tablicy jednowymiarowej? (żeby np. wcześniej wyliczone wartośći przechowywał i nie obliczał ich ponownie- tyle udało mi się wygooglować). Ma ktoś jakieś pomysły?

  
#include <iostream>
using namespace std;

int bezkrolikow (int n)
{
    if (n==0) return 4;
    if (n==1) return 7;
    
    return (2*bezkrolikow(n-1)) + (5*bezkrolikow(n-2));
}

int main() {
int t,n;

cin>>t;
for (int i=0;i<t;i++) 
{
    cin>>n;
    cout<<bezkrolikow(n)%2011<<endl;
}

    return 0;
} 

Ale jak to właśnie zaimplementować? w teorii też wiem że nalezy uzyć tablic

W pseudokodzie:

if(wartosc_jest_w_tablicy[n])
    return tablica[n];
else
{
    wartosc_jest_w_tablicy[n] = true;
    return (tablica[n] = oblicz_wartosc(n));
}

Link do zadania (zapewne na SPOJ). Jeśli to jest trwający konkurs to to źle trafiłeś.

Co do samego tematu:

• w takich zadaniach, część wyników można wpisać twardo w kod (najpierw trzeba napisać pomocniczy program, który obliczy wyniki).
• operacje modulo powinieneś włączyć już do rekurencji, ponieważ twoja funkcja jest bardzo szybko rosnąca (szybciej niż ciąg Fibonacciego), więc grozi ci przekroczenie zakresu int-a (operacja modulo temu zapobiegnie).
• radzę poczytać o właściwościach operacji modulo
• dla hipermądrych jest jeszcze coś takiego jak funkcje tworzące, pozwalające zamienić rekurencje na konkretny wzór.

Ja bym w ogóle tego tak nie robił. To jest proste jednorodne równanie rekurencyjne i bym je po prostu policzył.
a0=4
a1=7
an = 2a(n-1) + 5a(n-2)
Więc równanie charakterystyczne wygląda tak:
x² - 2x - 5 = 0 więc ze wzoru skróconego mnożenia mamy:
(x-1)² = 6 co daje nam od razu dwa potencjalne rozwiązania:
x1 = sqrt(6) + 1 lub x2 = 1 - sqrt(6)
W związku z tym rozwiązanie naszego równanie rekurencyjnego ma postać an = Ax1ⁿ + Bx2ⁿ
Podstawiając warunki początkowe uzyskujemy:
A+B=4
A*(sqrt(6)+1) + B*(1-sqrt(6)) = 7
z czego wychodzi nam że:
A = 2+sqrt(6)/4
B = 2-sqrt(6)/4
więc finalnie
an = (2+sqrt(6)/4)(sqrt(6)+1)ⁿ + (2-sqrt(6)/4)(1 - sqrt(6))ⁿ

dla sprawdzenia:
a0 = 2+sqrt(6)/4 + 2 - sqrt(6)/4 = 4
a1 = 4 + 12/4 = 4+3 = 7
a2 = 34 co potwierdza wolfram:
http://www.wolframalpha.com/input/?i=%282%2Bsqrt%286%29%2F4%29*%28sqrt%286%29%2B1%29%5En+%2B+%282-sqrt%286%29%2F4%29*%281+-+sqrt%286%29%29%5En+for+n+%3D+2

Więc jeżeli nigdzie sie nie walnąłem w obliczeniach (a ostatni raz liczyłem takie równanie na 1 roku na matematyce dyskretnej i było to 4 lata temu :D) to takie jest analityczne rozwiązanie dla tego ciągu ;]
Oczywiście istnieje pewien minus tego rozwiązania - jeśli będziemy je liczyć na jana to może nam się gdzieś rozjechać ze względu na niedokładność floatów, ale zasadniczo wszędzie nam się te sqrt(6) powinny upraszczać.
Bardziej się już tego chyba nie zoptymalizuje ;)

Nie jest to żaden konkurs, tylko szkolne zadanie, które zrobiłem (nie jest tylko zooptymalizowane)

Spoko, doświadczenie uczy, że trzeba być podejrzliwym (szczególnie wobec niezalogowanych).
W tym zadaniu zdecydowanie nie chodzi o to, żeby zwrócić dobry wynik (to jest bardzo łatwe), ale by pomyśleć na optymalizacją i otrzymać wynik w rozsądnym czasie.

Aby zoptymalizować program, powinieneś się pozbyć rekurencji. Funkcje rekurencyjne mają większą złożoność pamięciową i obliczeniową, niż algorytmy iteracyjne.
W przypadku Twojego programu, możesz przepisać funkcję rekurencyjną tak, aby korzystała ona ze zwykłej iteracji. Wystarczy, że będziesz zapamiętywał w każdej iteracji wartość bieżącą oraz wartość poprzednią i przypisywał je analogicznie do funkcji rekurencyjnej. Nie będzie Ci wtedy potrzebna żadna tablica, a jedynie 3 dodatkowe zmienne. Kod może wyglądać w sposób następujący:

int bezkrolikow(int n)
{
    int current = 0;
    int nMinusTwo = 4;
    int nMinusOne = 7;

    if (n==0) return nMinusTwo;
    if (n==1) return nMinusOne;

    if(n > 1) 
    {
        for(int i = 0; i < n - 1; i++) 
        {
            current = (2 * nMinusOne) + (5 * nMinusTwo);
            nMinusTwo = nMinusOne;
            nMinusOne = current;
        }
    }
    return current;
}