Rekurencja - zła praktyka?

0

Witam, chciałbym dowiedzieć się dlaczego rekurencja to zła praktyka? Dlaczego się tego nie używa?
Np. w obliczaniu silnii

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

ten przykład akurat nie jest najszczęśliwszy, bo kompilator zamieni to na pętlę (rekurencja ogonowa).

Fibonacci to lepszy przykład:

int fib(unsigned int x) {
     if (x<=0)
          return 0;
     if (x==1)
          return 1;
     return fib(x-1)+fib(x-2);
}

Problem polega na tym, że licząc fib(10) tą metodą obliczanie fib(8) następuje 2 razy fib(6) 4 razy fib(4) 8 razy itd. Daje to kwadratową złożonośc obliczeniową, co jest bardzo nieefektywne. Metodą iteracyjną można osiągnąć złożoność liniową.

0

a w tym konkretnym przypadku co lepiej zastosować? Iteracje?

2

ten przykład akurat nie jest najszczęśliwszy, bo kompilator zamieni to na pętlę (rekurencja ogonowa).

Nie.

Witam, chciałbym dowiedzieć się dlaczego rekurencja to zła praktyka?

Postawiles bzdurna teze i liczysz na jej wyjasnienie?

Petle zwykle sluza mutacji pewnego stanu, a rekurencja sluzy do obliczenia pewnej wartosci. Wiele definicji matematycznych/algorytmow sie opiera na rekurencji i nie, nie jest zla praktyka. Ba! Sa nawet jezyki, w ktorych to jedyny sposob na zrobienie 'petli'.

0
n0name_l napisał(a):

ten przykład akurat nie jest najszczęśliwszy, bo kompilator zamieni to na pętlę (rekurencja ogonowa).

Nie.

Witam, chciałbym dowiedzieć się dlaczego rekurencja to zła praktyka?

Postawiles bzdurna teze i liczysz na jej wyjasnienie?

Petle zwykle sluza mutacji pewnego stanu, a rekurencja sluzy do obliczenia pewnej wartosci. Wiele definicji matematycznych/algorytmow sie opiera na rekurencji i nie, nie jest zla praktyka. Ba! Sa nawet jezyki, w ktorych to jedyny sposob na zrobienie 'petli'.

Tezę postawiłem na podstawie tego co mi powiedzieli na rozmowie kwalifikacyjnej. Miałem napisać silnię i pierwszy sposób i ponoć najwydajniejszy to rekurencja (jak dla mnie). Nom i ludzie, którzy tam byli mówili, że tak się nie robi a jak zapytałem dlaczego to przeszliśmy do następnego pytania.

0

zobacz update mojej odpowiedzi.

4

Silnia, nawet jeśli kompilator tego nie zoptymalizuje, to niespecjalnie szczęśliwy wybór, bo int, albo nawet uint64_t ma za mało wartości, żeby dostrzec jej wady.

Rekursywnie często dużo prościej opisać wiele algorytmów, ale równie często skutkuje to zagnieżdżonymi wywołaniami funkcji, co potrafi wyczerpać stos i doprowadzić do zbędnego powtarzania obliczeń (patrz post @MarekR22 ). A do tego sam skok do funkcji jest całkiem drogi.

przykład:

for(int i = 1000000000; i; i--) cout << i << endl;

To się chwilkę będzie wykonywało, ale wykona się bezproblemowo, natomiast

void f(int i){
    cout << i << endl;
    if(i) f(i-1);
}
f(1000000000);

To powinno wywalić program, o ile tylko kompilator nie zoptymalizuje tego do pętli.

1

To zależy. Jeżeli w przypadku bardziej zaawansowanych języków jest jak najbardziej w porządku (jak w spomniano, w niektórych robi się tylko tak). W przypadku C i C++ można spokojnie stosować w większości przypadków, ale warto wiedzieć, że każde wywołanie wymaga odrobiny miejsca na stosie. Na PCcie prawdopodobnie przepełnisz stos (przez co program się najczęściej wysypie) tylko jeśli będziesz miał zły warunek stopu i funkcja będzie się wywoływać w nieskończoność, ale gdybyś miał programować mikrokontroler być może należy wziąć taką ewentualność pod uwagę. Z kolei rekurencja jest często czytelniejsza..

3

Budda Siakjamuni powiedział:

Nie wierzcie w jakiekolwiek przekazy tylko dlatego, że przez długi czas obowiązywały w wielu krajach. Nie wierzcie w coś tylko dlatego, że wielu ludzi od dawna to powtarza. Nie akceptujcie niczego tylko z tego powodu, że ktoś inny to powiedział, że popiera to swoim autorytetem jakiś mędrzec albo kapłan, lub że jest to napisane w jakimś świętym piśmie. Nie wierzcie w coś tylko dlatego, że brzmi prawdopodobnie. Nie wierzcie w wizje lub wyobrażenia, które uważacie za zesłane przez boga. Miejcie zaufanie do tego, co uznaliście za prawdziwe po długim sprawdzaniu, do tego, co przynosi powodzenie wam i innym.

To samo się tyczy wszystkich poglądów w IT, zwłaszcza tak prostych do sprawdzenia. Napisz dwie wersje rozwiązania tego samego problemu i zmierz wydajność obu rozwiązań. W niektórych językach/kompilatorach/ustawieniach kompilatora etc. rekurencja może działać świetnie, w innych gorzej. Sprawdź sam, a nauczysz się najwięcej.

1

Jak chcesz wiedzieć jak działa rekursja od podszewki to polecam:
http://flint.cs.yale.edu/cs422/doc/art-of-asm/pdf/CH11.PDF

5
elwis napisał(a):

To zależy. Jeżeli w przypadku bardziej zaawansowanych języków jest jak najbardziej w porządku (jak w spomniano, w niektórych robi się tylko tak). W przypadku C i C++ można spokojnie stosować w większości przypadków, ale warto wiedzieć, że każde wywołanie wymaga odrobiny miejsca na stosie.

Na stosie odłożony zostaje rejestr EIP i bodajże CS, przeważnie też ESP i EBP oraz wartości parametrów wywołania funkcji. Przy powrocie z funkcji wszystkie te wartości są zdejmowane. Samą operację skoku pomijam, bo pętla też ją zawiera. To zajmuje ileś cykli procesora, rząd wielkości (albo i dwa) więcej, niż jakakolwiek prosta operacja (typu dodawanie czy mnożenie) wykonywana przez taką funkcję. Oznacza to, że rekurencyjne wykonywanie prostej operacji jest zawsze marnowaniem mocy obliczeniowej procesora. Jednak im więcej obliczeń robi funkcja wykonywana rekurencyjnie, tym narzut spowodowany operacjami na stosie robi się relatywnie mniejszy, aż w pewnym momencie jest pomijalny.
Jednak pamiętajmy o tym, że optymalizuje się tylko wąskie gardła. W każdym innym miejscu najważniejsza jest czytelność kodu. Jeśli rekurencja znacząco upraszcza zapis algorytmu nie wpływając istotnie na wydajność aplikacji, to należy jej użyć.

0

Dziękuję za pomoc. Muszę sobie jeszcze to wszystko przemyśleć bo jak widać zdania są dość podzielone :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1