• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Teoria a praktyka , Iteracyjnie a rekurencyjnie .

Object Storage Arubacloud
0 głosów
1,514 wizyt
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.smileyyes 

3 odpowiedzi

+3 głosów
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 :) 

+1 głos
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

–1 głos
odpowiedź 1 czerwca 2018 przez Alex.Ironside Stary wyjadacz (14,900 p.)
Bardzo dobrze wyjasnione w filmie Pana Zelenta. https://youtu.be/jNi_X5bvmQ0

Podobne pytania

0 głosów
1 odpowiedź 6,331 wizyt
pytanie zadane 11 kwietnia 2017 w C i C++ przez hacker09 Użytkownik (520 p.)
0 głosów
1 odpowiedź 329 wizyt
pytanie zadane 10 października 2021 w C i C++ przez yato_ Początkujący (350 p.)
0 głosów
1 odpowiedź 318 wizyt
pytanie zadane 17 listopada 2020 w C i C++ przez ifuknowme555 Początkujący (410 p.)

92,662 zapytań

141,557 odpowiedzi

320,002 komentarzy

62,029 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...