Przepełnienie stosu

[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.