Przepełnienie stosu przy generowaniu ciągu Fibonacciego

Napisałem mały algorytm do zadanka na spoju, wszystko śmiga dopóki n<3550 (+/-). dalej następuje przepełnienie stosu. Prawdę mówiąc spędziłem już dobrych kilka godzin na próbach obejścia tego problemu, ale nic z tego. Nienawidzę się poddawać, ale na prawdę nie mam już pomysłów. Da się jeszcze jakoś uratować ten kod? czy najlepiej wyrzucić go do śmieci, przemyśleć od nowa i z całkiem innej strony podejść do niego?

#include <iostream>

using namespace std;

unsigned long long fibW = 0;
unsigned long long fibM = 1;
int k = 1;

unsigned long long fib(int n)
{
    unsigned long long help;
    help = fibM;
    fibM = fibW;
    fibW = help + fibM;

    if (fibW >= 1000000007)
    {
        fibW = fibW % 1000000007;
    }

    if (n == 1 || n == 2) return fibW;
    else if(n == k)
    {    
        return fibW;
    }
    else
    {
        k++;
        return fib(n);
    }
}

int main()
{   
    unsigned long long wynik[100];
    int ilosc; cin >> ilosc;
    for (int i = 0; i < ilosc; i++)
    {
        int n; cin >> n;
        wynik[i] = fib(n);
        fibM = 1;
        k = 1;
        fibW = 0;
    }
    for (int i = 0; i < ilosc; i++)
    {
        cout << wynik[i]<<endl;
    }

}

Zamien implementacje na iteracyjna i problem bedzie rozwiazany.

@ɹedɔaʞ: Poczytaj sobie o memoizacji.

Przepełnienie stosu wynika z tego, że każde wywołanie alokuje parametry i zmienne lokalne na stosie, a zatem dla dużych liczb dostajesz przepełnienie stosu. Z tego co widzę, masz rekursję ogonową, więc chyba możesz bezpiecznie zrobić zmienną help jako static albo zmienną globalną, w ten sposób zredukujesz wykorzystanie stosu bodajże o połowę (na x86_64). Twoja implementacja i tak nie jest wielobieżna. A tak generalnie to chyba i tak lepiej zrobić to iteracyjnie.

1. Najwyraźniej kompilator którego uzywłeś na SPOJ nie wykrywa możliwej optymalizacji tail recursion (kompilator zamienia rekursję na pętlę), a na twojej lokalnej maszynie, kompilator to potrafi dla tego kodu
2. Tak jak napisał winuser zrób wersję iteracyjną
3. Wersja iteracyjna i wykorzystująca memoizacę to za mało, trzeba zainwestować troszkę więcej szarych komórek:
   • zainteresować się np Pisano Period (dla 1000000007 bedzie to pewnie duża wartość)
   • można jeszcze wykorzystać macierz 2x2 i algorytm szybkiego potęgowania, do przyspieszenia obliczeń (z O(n) zrobi się O(log n)).

w fib(n) wywołujesz znowu fib(n) bez zmiany wartości n, czyli wpadasz w nieskończoną pętlę tam

https://godbolt.org/z/aeEszzGEa