Rekurencja i przepełnienie stosu

[Antystatyczny]

Witam,

Usiłowałem wczoraj opanować funkcje rekurencyjne i postanowiłem przecwiczyć temat generując ciąg Fibonacciego. Po kilku nieudanych próbach wygenerowałem ciąg liczb. Ok, najpierw kod:

Kod: Zaznacz cały

#include<iostream>

using namespace std;


unsigned int fib = 0;

void fibonaci(unsigned int val);


int main(void)
{
   fibonaci(fib);

   system("pause");

   return 0;
}

void fibonaci(unsigned int val)
{
   static unsigned int last_value;//poprzednia wartosc "val"
   unsigned int temp = val;
   cout << val << endl;//wyswietlenie aktualnych danych

   val += last_value;//dodaję poprzednią wartość do obecnej
   last_value = temp;//odtwarzam wartość val i od tej pory jest jako poprzednia

   //zeby wygenerowanie ciągu  doszło do skutku, nalezy zwiększyć wartość o jeden, gdy val == 0
   if (!val) val++;
   if (val > 0xFFFFFFF0) return;
   fibonaci(val);
}

Nie jest to nic wyrafinowanego, z C++ też ma niewiele wspólnego. Problemem jest przepełnienie stosu podczas próby wygenerowania ciągu kończącego się w okolicach limitu dla unsigned int. I tu pytanie... W jaki sposób ustalić co przepełniło stos? Odkłądane adresy powrotu z funkcji (liczyłem na to, że funkcja rekurencyjna będzie ogonową) czy coś innego? Mam pewne podejrzenia, że kopie argumentu val odkładane sa na stos, ale w takim razie jak przekazać zaktualizowany argument do kolejnego wywołania funkcji rekurencyjnej?

Przychodzi mi na myśl wskaźnik do zmiennej globalnej, ale to by się kłóciło z sugestią, by ograniczać ilość zmiennych globalnych

[mokrowski]

Skompiluj program w trybie debug i jak się wywróci zanalizuj go debugerem. Zapewne wywrócił się przez odłożenie ramki na stosie która zawiera adres powrotu oraz argumety wywołania.
Jeśli chcesz mieć możliwość użycia rekurencji dla dużej ilości wywołań, należy przekształcić wywołania na tzw. rekurencję ogonowową (ang. tail recursion) https://pl.wikipedia.org/wiki/Rekurencja_ogonowa Wtedy nie jest przepełniany stos a jedynie w programie jest skok (jmp) a nie wywołanie (call).
Tu masz przykład fibonacciego z rekurencją ogonową:

Kod: Zaznacz cały

#include <iostream>

typedef unsigned long long int ullint;

ullint fiboTail(int n, ullint a, ullint b)
{
      if (n == 0) return a;
      if (n == 1) return b;
      return fiboTail(n - 1, b, a + b);
}

int main() {
    using namespace std;
    cout << fiboTail(90, 0, 1) << endl;
}

Możesz sprawdzić że nawet dla 90 wyrazu, zwraca wartość i nie konsumuje stosu

[PROTON]

Stos konsumuje bo ten warunek nigdy nie jest spełniony:

Kod: Zaznacz cały

if (val > 0xFFFFFFF0) return;

[mokrowski]

Tu masz wersję "klasyczną". W zależności od maszyny, będzie przepełnianiała stos lub wykonywała się dłuuuugo

Kod: Zaznacz cały

#include <iostream>

typedef unsigned long long int ullint;

ullint fibonacci(unsigned n)
{
    if(n < 2) {
        return n;
    }
    return fibonacci(n - 2) + fibonacci(n - 1);
}

int main()
{
    using namespace std;

    unsigned index;
    cout << "Podaj indeks w ciągu Fibonacciego, licząc od 0: ";
    cin >> index;
    cout << "Wartość w ciągu Fibonacciego dla indeksu " << index << " to: "
        << fibonacci(index) << endl;
}

[mokrowski]

Masz tu jeszcze "klasyczne podejście" do silni:

Kod: Zaznacz cały

#include <iostream>

typedef unsigned long long int ullint;

ullint silnia(unsigned n)
{
    if(n == 0)
    {
        return 1;
    }
    return silnia(n - 1) * n;
}

int main()
{
    using namespace std;
    unsigned index;
    cout << "Podaj dla jakiej liczby policzyć silnię: ";
    cin >> index;
    cout << "Silnia dla liczby " << index << " to: " << silnia(index) << endl;
}

.. i to samo "ogonowo":

Kod: Zaznacz cały

#include <iostream>

typedef unsigned long long int ullint;

ullint silnia(unsigned n, ullint sum = 1)
{
    if(n == 0)
    {
        return sum;
    }
    else
    {
        return silnia(n - 1, n * sum );
    }
}

int main()
{
    using namespace std;
    unsigned index;
    cout << "Podaj dla jakiej liczby policzyć silnię: ";
    cin >> index;
    cout << "Silnia dla liczby " << index << " to: " << silnia(index) << endl;
}

Możesz sobie porównać co szybciej przeciąży stos

[Antystatyczny]

Stos konsumuje bo ten warunek nigdy nie jest spełniony:

Kod: Zaznacz cały

if (val > 0xFFFFFFF0) return;

A mógłbyś odrobinkę wyjaśnić, dlaczego nigdy nie jest spełniony?

@mokrowski: klasyczny przykład programu faktycznie oblicza liczbę całe wieki, a wersja ogonowa w ułamku sekundy... Szczerze mówiąc nie bardzo czuję, dlaczego róznice w czasie obliczenia są tak dramatyczne, nawet podczas obliczenia liczby z ciągu o indeksie 50.

Poza tym, po przeczytaniu i usiłowaniu zrozumienia opisu funkcji ogonowej, stwierdziłem, że moja wersja funkcji również powinna być ogonową, bo ostatnim poleceniem, jakie wykonywała funkcja, było wywołanie jej samej. Czegoś tu ewidentnie nie dostrzegam lub nie rozumiem

[PROTON]

Zostawiłeś za małe okienko aby w nie trafić.

Kod: Zaznacz cały

if (val > 0xFFFFFFF0) return;

Jakie wartości val musi przyjąć aby warunek został spełniony?

Bardzo mało:

0xFFFFFFF1
0xFFFFFFF2
0xFFFFFFF3
0xFFFFFFF4
0xFFFFFFF5
0xFFFFFFF6
0xFFFFFFF7
0xFFFFFFF8
0xFFFFFFF9
0xFFFFFFFA
0xFFFFFFFB
0xFFFFFFFC
0xFFFFFFFD
0xFFFFFFFE
0xFFFFFFFF

Im dalszy element ciągu tym szybciej rośnie, w tym przypadku bezpiecznie jest przyjąć:

Kod: Zaznacz cały

if (val > 0xEFFFFFFF) return;

[Antystatyczny]

Ok, ok...to przeoczyłem. Faktycznie, skok o 1 w indeksie może spowodować, że wartość val może wzrosnąć o znacznie więcej niż 0xF i wtedy val ulegnie przepełnieniu i w dalszym ciągu warunek nie bedzie spełniony

[mokrowski]

1. Rekurencja ogonowa jest wtedy gdy funkcja zwraca wynik z samą sobą lub wartość obliczoną. Wyklucza to jakieś sumy, sumy/mnożenia ze sobą i inne "kwiatki".
Inaczej ogonową można zrozumieć tak: Kompilator łatwo orientuje się że zbędne są wyniki poprzednich wywołań funkcji i nie ma sensu ich trzymać.
Dlatego w wersji fibo "z ogonem", masz przekazywaną "pamięć" poprzednich wywołań Tak więc kompilator łatwo dowiaduje się że nie ma sensu trzymać ramek stosu poprzednich wywołań. Są zbędne.
2. Ogonowa jest szybsza bo:
- zbędne jest hurtowe zwijanie stosu
- zbędne ciągłe odkładanie na stos elementów wywołania
- kompilator nie wstawia "call" tylko zwykły skok "jmp" lub instrukcję warunkową

[Antystatyczny]

Ok, czyli moim błedem było dokonywanie obliczeń wewnątrz funkcji oraz ich zapamietywanie. To wymuszało na kompilatorze zapamiętywanie tych wartości i przez to funkcja nie mogła zostać przekształcona w ogonową. Postaram się to przećwiczyć od tej strony