Przepełnienie stosu

[wlefix]

Witam!
Napisałem program, który opiera się na rekurencji, niestety po wywołaniu funkcji 179 raz wyskakuje mi komunikat "Przepełnienie stosu", a moja rekurencja, by dobrze zadziałała musi wykonać jedyne  46 000 000 wywołań. Czy da się na to jakoś zaradzić? Myślę, że obniżenie ilości powtarzania funkcji nie wchodzi w grę. Dziękuję za pomoc.

[Simbax]

Nie jestem pewien, czy CBOT to optymalizuje, ale jeśli tak, to spróbuj przekształcić tę funkcję do postaci rekurencji ogonowej, tzn. rekurencyjne wywołanie musi być ostatnią operacją. Ewentualnie ręcznie napisać postać iteracyjną. Przepełnienia stosu raczej trudno uniknąć w inny sposób, taka jest natura funkcji rekurencyjnych. Podniesienie limitu do 46 mln raczej nie wchodzi w grę, chyba że to sztuczne ograniczenie nie wynikające ze sprzętu.

Edit:

Z ciekawości sprawdziłem, czy CBOT potrafi optymalizować rekursję ogonową, i wychodzi na to, że nie potrafi... Przetestowałem na funkcji liczenia silni.

Code:

int fact(int n)
{
    if (n == 1 || n == 0) return 1;
    return n * fact(n - 1);
}

int fact_tail(int n)
{
    return fact_tail_(n, 1);
}

int fact_tail_(int n, int a)
{
    if (n <= 1) return a;
    return fact_tail_(n - 1, a * n);
}

int fact_iter(int n)
{
    // fact_tail_(n, 1);
    int a = 1;
    while(true)
    {
        if (n <= 1) return a; // return a
        a = a * n;
        n = n - 1;
        // fact_tail_(n - 1, a * n);
    }
    return -1; // to make it compile
}

extern void object::TestTailRecursion()
{
    
    // Both cause stack overflow...
    //fact(200);
    //fact_tail(200);
    fact_iter(200); // Ok
    
}

fact_iter na pierwszy rzut oka wygląda dziwnie, ale w istocie pokazuje w jaki sposób można zmienić funkcję z rekurencją ogonową na wersję iteracyjną.

Ciekawostka: g++ z opcją -O2 optymalizuje zarówno pierwszą wersję jak i drugą, bez -O2 (lub z niższą optymalizacją, np. -O1) obydwie potrafią wywołać przepełnienie stosu.

BTW 46 mln wywołań to bardzo dużo, zwłaszcza dla CBOTa. Proponuję odpalić poniższy program:

Code:

for (int i = 0; i < 46000000; ++i)
{
        
}

U mnie i dochodzi do 10000 dopiero po kilku sekundach. Nawet program w C++ie by "chwilę" działał. CBOT jest zbyt wolny niestety do takich zabaw.

[tomangelo]

Potwierdzam, o ile program w C++ wykonuje zadanie (46 mln powtórzeń pustej pętli) w około sekundę (bez optymalizacji gcc), tak CBot potrzebuje na to zadanie znacznie większego czasu, 10000 powtórzeń tej pętli to około 20 sekund, więc wykonanie 46 milionów powtórzeń zajęłoby przynajmniej cały dzień. A jeśli wewnątrz jest jakiś bardziej skomplikowany algorytm, to zadanie może się strasznie przeciągnąć.
W takim razie trzeba raczej pomyśleć o nierekurencyjnym algorytmie.