Rekurencja a iteracja :D

Question

Siemanko robiłem zadanie z odc. 13. Dla ciągu fibonacciego, metodą rekurencji i iteracji.

Otóż-  wyszło mi, że iteracja jest o wiele szybsza o dziwo? Dla 44 wyrazu ciągu 4 sekundy zajęło obliczenie rekurencji natomiast iteracji 0.001, jakim cudem tak rozbierzny wynik? Za każdym razem iteracja jest szybsza  :D a to przecież rekurencje stosujemy w przypadku przyspieszenia pracy kosztem pamięci

Answer 1

To zależy. I nie ma reguły, że rekurencja będzie zawsze szybsza od metody iteracyjnej i na odwrót. Są zagadnienia, które lepiej się rozwiązuje metodą rekurencyjną, a czasami lepiej jest użyć innej metody, np. iteracyjnej.

"Czy ferrrari z silnikiem od fiata 126p, będzie szybsze niż fiat 126p z silnikiem ferrari?"

To pytanie zostawie dla Was...

Szybkość wykonania programu, zależy tylko od programisty! Od tego jak wykorzystuje zasoby komputera, jaki napisze alogorytm i oczywiście jaką ma znajomość działania komputera. Rekurencja pomimo wielu zalet, ma też poważne wady. Np. to, że ilośc wywołań jest ograniczona wielkością stosu(tutaj zapraszam do lektury na temat stosu i sterty).

Różnica którą zaoberwowałeś w swoim kodzie wynika pewnie z mało optymalnej metody. Pozwolę sobie wkleić kod użytkownika Radfler. Z czasu wykonania pewnie wynika, że u siebie masz podobną implementację.

//Metoda rekurencyjna
unsigned long long fib(unsigned long long n)
{
    if(n > 2)
        return fib(n-1) + fib(n-2);
    return 1;
}

//Metoda iteracyjna
unsigned long long fib_i(int num) { 
    unsigned long long x=1, y=1;
    while(--num) x = (y += x) - x;
    return x;
}

Moja implementacja:

//Zoptymalizowana rekurencja
unsigned long long fib_optimized(int n, unsigned long long n1 = 1, unsigned long long n2 = 1)
{	
	if(n == 2)
		return n2;
	return fib_optimized(n - 1, n2, n1 + n2);
}

Jak widac na powyższym przykładzie, rekurencja może być tak samo szybka jak metoda iteracyjna, albo nawet i szybsza... Wszytsko zależy od programisty!

Answer 2

Daj kod, bo aż uwierzyć nie mogę :o

Comments

Zazwyczaj rekurencja jest wolniejsza, bo obliczenia się powtarzają. 

---

Rzeczywiście, sam napisałem taki program i wynika z niego, że rekurencja dla większych elementów jest wolniejsza o nawet sekundę :/

#include <iostream>
#include <ctime>
using namespace std;

inline int fib_r(int num) {

    return (num < 3) ? (1) : fib_r(num-2)+fib_r(num-1);
}

int fib_i(int num) {

    int x=1, y=1;
    while(--num) x = (y += x) - x;
    return x;
}

int main() {

    const int nr_wyrazu = 40;

    double start, stop; // double zamiast clock_t (czyli long)
    int rezultat;

    cout.precision(20); // Precyzja wypisywania

    // Około 1.9530000000000000693 sekundy
    start = clock();
    rezultat = fib_r(nr_wyrazu);
    stop = clock();
    cout << "Czas [metoda rekurencyjna]: " << (stop-start) / CLOCKS_PER_SEC
         << "\trezultat = " << rezultat << endl << endl;

    // 0 sekund
    start = clock();
    rezultat = fib_i(nr_wyrazu);
    stop = clock();
    cout << "Czas [metoda iteracyjna]: " << (stop-start) / CLOCKS_PER_SEC
         << "\trezultat = " << rezultat << endl << endl;
}

 

Answer 3

Zapewne funkcja rekurencyjna wygląda tak:

int fib(int n)
{
    if(n > 2)
        return fib(n-1) + fib(n-2);
    return 1;
}

Narysuj sobie drzewo wywołań funkcji nawet dla niewielkich wyrazów, a zobaczysz, że część obliczeń się powtarza. Przy 44 wyrazie powtórzeń jest tak wiele, że kod wykonuje się setki razy dłużej niż dla iteracji.

Moim zdaniem rekurencja nie jest w żaden sposób wydajniejsza, ale zapisany algorytm jest bardzo zgrabny, natomiast iteracja nie wygląda tak pięknie ale kod jest często dużo szybszy i nie zużywa tak wiele pamięci.

Answer 4

To nie dziwne. Dodawanie jest bardzo 'przyjemne' dla procesora. Poczytaj sobie jak działa na przykład mnożenie, albo napisz sobie coś na liczenie silni obydwoma sposobami.