Teoria a praktyka , Iteracyjnie a rekurencyjnie .

pytanie zadane 1 czerwca 2018 w C i C++ przez qlucha Obywatel (1,790 p.)

Witam, mam dzisiaj pytanie typowo teoretyczne i prosiłbym o proste wyjaśnienie na początek dlaczego tak jest.

Otóż, ciekawi mnie fenomen przewagi rekurencji nad metodą iteracyjną . Chodzi mi o szybkość działania algorytmu .

Jak podejść do problemu aby dobrze to zrozumieć, skoro na pierwszy rzut oka jeśli chodzi o działanie obu metod działają podobnie, chodzi mi o to że:

Iteracyjnie działamy w pętli , w każdej iteracji pętli następuje wykonanie pewnych instrukcji i przejście do następnej iteracji . Czyli stąd mój wniosek że, następna iteracja musi czekać na zakończenie działania poprzedniej co musi potrwać .

rekurencyjnie - zanim funkcja wywoła samą siebie i utworzy swoją kopie, też musi poczekać z wywołaniem własnej kopi do czasu wykonania instrukcji zawartych w ciele funkcji i sprawdzenia czy przypadek tak zwany podstawowy nie jest Prawdą.

Czyli obie metody na pierwszy rzut oka działają w ten sam sposób, gdzie jest tak zwany haczyk ?

(rozpisałem się bardzo ogólno-poglądowo, jestem ciekaw każdej wartościowej opini ) dzieki.

3 odpowiedzi

odpowiedź 1 czerwca 2018 przez RafalS VIP (122,820 p.)

Nie wiem skąd pomysł, że rekurencja jest lepsza od iteracji. Otóż w językach imperatywnych jak C, C++, Java, C# rekurencja jest wolniejsza od iteracji! Czemu? Języki te operują na zmiennych automatycznych na stosie. Oznacza to, że dla każdego wywołania iteracyjnego trzeba zaalokować na stosie oddzielny zestaw zmiennych lokalnych. Nie wiem czemu miało by to być szybsze od iteracji. A jak już mówimy o stosie to mam nadzieję, że znasz wyjątek stackoverflow, czyli przepełnienie stosu, który przeważnie ma tylko kilka MB pojemności u mnie 1.5 MB. Głębokie zagnieżdzanie rekurencyjne bardzo szybko więc przepełni stos.

Jest też coś takiego jak tail-recursion optimization. Oznacza to, że jeśli kompilator zauważy ogonową rekurencję, czyli taką gdzie wywołanie rekurencyjne jest ostatnią operacją w funkcji to zooptymalizuje rekurencję do pętli. Czemu - iteracja jest bezpieczniejsza (przepełnienie stosu) i szybsza.

Iteracja jest też przeważnie o wiele czytelniejsza od rekurencji, co jest ogromnym atutem.

Wg mnie rekurencji powinno się używać tylko w przypadkach gdy problem jest tak skonstruowany, że użycie rekurencji jest albo konieczne albo dodaje czytelności tzn da się coś napisać pętlą ale byłoby to strasznie przekombinowane a z rekurencją kod wygląda zgrabniej i czytelniej.

komentarz 1 czerwca 2018 przez criss Mędrzec (172,590 p.)

Dorzuce link https://medium.com/@felipedutratine/iterative-vs-recursive-vs-tail-recursive-in-golang-c196ca5fd489

jeśli kompilator zauważy ogonową rekurencję, czyli taką gdzie wywołanie rekurencyjne jest ostatnią operacją w funkcji to zooptymalizuje rekurencję do pętli.

Generalnie chodzi o to, że używana jest ponownie ta sama ramka stosu. Chyba można to nazwać "optymalizacją do pętli", ale tak ukonkretniam :)

odpowiedź 1 czerwca 2018 przez k222 Nałogowiec (30,150 p.)

Nie ma zasady że rekurencja jest szybsza i koniec.

O tym który algorytm jest szybszy decyduje złożoność obliczeniowa - jeżeli jeden algorytm dla n wpisanych liczb zrobi n operacji a drugi n*n operacji, to ten pierwszy będzie szybszy i to jest jedyny wyznacznik, trzeba oszacować złożoność algorytmu i będziesz miał czarno na białym - np. algorytmy sortowania (o których pewnie słyszałeś) : sortowanie bąbelkowe ma złożoność n*n a quicksort n*log(n), dlatego jest szybszy, ale przy określonych danych można dojść do metody iteracyjnej która będzie miała złożoność n (CountingSort).

Co do samej rekurencji to nie służy ona po to żeby coś przyspieszyć, bo sama w sobie jak będzie miała taką samą złożoność jak pętla for to nic nie przyspieszy, stosuje się ją najczęściej po to że są problemy pod nią stworzone - takie, które za pomocą rekurencji bardzo łatwo zapisać i efektywnie działają (np. operacje na strukturze zwanej drzewem) , a chcąc zapisać je iteracyjnie trzeba by kombinować z kolejkami, stosami czy tym podobnymi tworami.

komentarz 1 czerwca 2018 przez criss Mędrzec (172,590 p.)

O tym który algorytm jest szybszy decyduje złożoność obliczeniowa - jeżeli jeden algorytm dla n wpisanych liczb zrobi n operacji a drugi n*n operacji, to ten pierwszy będzie szybszy i to jest jedyny wyznacznik, trzeba oszacować złożoność algorytmu i będziesz miał czarno na białym

No nie, to jest podejście teoretyczne kompletnie ignorujące rzeczywistość. To czy algorytm jest zaimplementowany rekurencyjnie (gorzej) czy iteracyjnie (lepiej) robi zasadniczą różnicę. Wpływ będą miały też użyte instrukcje (SIMD?), architektura jednostki wykonawczej (niekoniecznie CPU) czy rozmiar dostępnej pamięci cache. Niektóre algorytmy można też zrównoleglać, a nie zmienia to przecież złożoności obliczeniowej więc mamy kolejny czynnik. Profesjonalnie implementując/projektując algorytm wszystko to powinieneś brać pod uwagę.

Zobacz odpowiedź RafalS