Problem z rekurencją i czasem

Question

Cześć,

Mam problem z kodem. Mam za zadanie wyliczyć czas zapisu przy pomocy iteracji i rekurencji. Przy iteracji normalnie działa, ale przy rekurencji wywala mi program. Mógłby ktoś naprowadzić mnie dlaczego dzieje się tak a nie inaczej?

#include <iostream>
#include <time.h>

using namespace std;

long int fib (int n)
{
    if (n == 1 || n == 2) return 1;
    else return fib(n - 1) + fib(n - 2);
}

clock_t start, stop;
double czas;
int ile;

int main()
{
    cout << "Czas zapisu iteracyjnie" << endl;
    cout << "Ile liczb ciagu Fibonacciego chcesz obliczyc: ";
    cin >> ile;

    //poczatek liczenia fib iteracyjnie
    int *tablica = new int [ile];
    tablica[0] = tablica[1] = 1;

    start = clock();

    for (int i = 2; i < ile; i++)
        tablica[i] = tablica[i - 1] + tablica[i - 2];
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "Czas iteracyjnie wynosi: " << czas << endl;

    delete [] tablica;

    cout << "Czas zapisu rekurencyjnie" << endl;
    start = clock();
    fib(ile);
    stop = clock();
    czas = (double)(stop - start) / CLOCKS_PER_SEC;
    cout << "Czas rekurencyjnie wynosi: " << czas;

    return 0;
}

 

Answer 1

Wywala mi program?

Coś więcej? Crashuje? Być może nadpis zmiennej nie działa - spróbuj zakomentarzować część iteracyjną i powiedz, czy zadziałało. Jeśli tak, to stwórz zmienne start2, stop2 i po kłopocie...

Comments

Normalnie w konsoli wpisuje wartosc ile, to dla iteracyjnego działa, a gdy ma przejść do rekurencji, to wyświetla pierwszego cout'a i pokazuje

Program przestał działać

U Pana Mirosława na jedynym z filmików obliczał czas ze wskaznikami i bez i miał użyte te same zmienne do liczenia czasu.

Po wykomentowaniu iteracyjnego, ten sam błąd.

---

Czyli problemem prawdopodobnie jest sama rekurencja.

---

Domyślam się.

---

U mnie twój kod działa...

 

Czas zapisu iteracyjnie
Ile liczb ciagu Fibonacciego chcesz obliczyc: 30
Czas iteracyjnie wynosi: 0
Czas zapisu rekurencyjnie
Czas rekurencyjnie wynosi: 0.042

---

Spróbuj np. dla 1000000 wyrazów.

---

Spróbuj np. dla 1000000 wyrazów.

Kolego, narzut pamięci spowodowany tyloma wywołaniami rekurencji [w twoim przypadku * 2] może doprowadzić do przepełnienia stosu, a w efekcie crashu programu.

Narzut dobrze może zobrazować poniższy przykład - każde wywołanie rekurencji tworzy kopie zmiennej:

void Rekurencja( int Ktore_Wywolanie )
{
    if( Ktore_Wywolanie > 0 )
    {
        std::cout << "Wartosc liczby: " << Ktore_Wywolanie << ". Adres zmiennej w pamieci: " << &Ktore_Wywolanie << std::endl;
        Rekurencja( Ktore_Wywolanie - 1 );
    }

    std::cout << "Teraz wrocilem tutaj. Zmienna wynosi: " << Ktore_Wywolanie << ". A adres: " << &Ktore_Wywolanie << std::endl;
}

 

---

Tak mi się zdawało, bo tak właśnie rekurencja działa, ale chciałem się upewnić. :)

Answer 2

Twój kod działa poprawnie, ale algorytm wyznaczania kolejnych liczb ciągu fibonacciego oparty na rekurencji jest bardzo niewydajny. Można to dobrze zaobserwować na przedziale liczb ok 40-48 :)

Comments

Jest to zadanie domowe z odcinka 13 u Pana Mirosława. Pomyslałem, że zrobię to na ciągu fibonacciego, bo dość często męczą o to na rozmowach i warto to wiedzieć.

---

Algorytm na wyznaczanie liczb ciągu fibonacciego jak najbardzij warto znać, ale w tym przypadku znacznie wydajniejszy będzie algorytm iteracyjny ;)

---

Tak, domyślam się, bo Pan Mirosłąw dość jasno wyjaśnił działanie rekurencji. :)