Algoritmi recursivi vs iterativi

Recent am inceput sa rezolvam probleme la info, folosind algoritmi recursivi. Sunt multe probleme pe care pot sa le rezolv iterativ in 2 minute, dar pur si simplu nu imi dau seama cum ar trebui sa fac algoritmul recursiv. Exista vreun avantaj al algoritmilor recursivi, sau alegerea modului de rezolvare depinde doar de "gusturile" programatorului?

Edited by reaper666, 14 March 2013 - 16:38.

Scrie o "cautare binara/divide et impera" recursiv si vezi cum arata.

 reaper666, on 14 martie 2013 - 16:37, said:

Codul recursiv ii cod mai curat, mai elegant, de multe ori mai usor de inteles etc. dar depinde de situatie deoarece (o problema importanta) nu poti apela recursiv o functie la infinit fiindca orice apel al functiei salveaza in stiva starea si cum stiva nu este infinita, la un moment dat programul iti va crapa cu stackoverflow.

 jm2010, on 14 martie 2013 - 16:47, said:

Aici tind sa te contrazic. Algoritmii recursivi sunt de obicei mai eleganti (daca prin elengant vrei sa zici mai compacti), dar mai curat sau usor de inteles n-as crede.

Iterativ, parerea mea, e mai usor de inteles aproape orice algoritm, dar e mai greu de scris.

Ne poti arata o varianta iterativa mai "usor de inteles" decat cea recursiva pentru listarea unei structuri de directoare?

 nucL3ar, on 14 martie 2013 - 16:55, said:

Statistic nu ai dreptate. Dar particular la modul tau de a percepe ai, nimeni nu poate sa contrazica simturile tale.

Edited by neagu_laurentiu, 14 March 2013 - 17:06.

 reaper666, on 14 martie 2013 - 16:37, said:

Avantaje algoritmi recursivi:
- sunt mai simpli de scris, dacă ai înţeles problema (recursivă), sau datele (recursive, izomorfe)
- ca elev, te fac să gândeşti altfel
- poţi oricând să-i "linearizezi", deci arunci la grămadă un algoritm recursiv în faza de prototyping, şi mult mai încolo te poţi gândi la eficientizare

Avantaje algoritmi iterativi:
- mai performanţi, nu încarcă stiva, nu pierzi controlul asupra memoriei (în special a fragmentării). O stivă consumată e un pericol real în orice program mai complex care foloseşte algoritmi recursivi

Notă: numărul de avantaje e irelevant, şi probabil mai lipsesc alte avantaje din acest tabel.

Singurul avantaj al algoritmilor recursivi apare in momentul in care nu poti rezolva problema altfel (iterativ), sau ar fi prea dificil.
De exemplu, e absurd sa calculezi recursiv factorialul unui numar; dar problema turnurilor din Hanoi are sens.

 TS030, on 14 martie 2013 - 22:19, said:

Depinde de problema. Adevarul este ca pentru un incepator in programare, algoritmii recursivi par foarte greu de inteles si de cele mai multe ori prefera algoritmii iterativi. Un programator cu experienta va prefera cam intotdeauna algoritmii recursivi in locul celor iterativi atunci cand se pot folosi ambele variante. Dar depinde de tipul problemei si depinde de nivelul de experienta.

 jm2010, on 15 martie 2013 - 08:43, said:

Nu stiu ce fel de programator cu experienta e ala, dar eu l-as da afara.

 TS030, on 15 martie 2013 - 10:09, said:

Hmmm, un programator care nu s-ar obosi sa lucreze pentru tine. Si eu m-am referit la programatori cu experienta adevarat nu la cei la care experienta relevanta se masoara doar in anii in care a stat la aceeasi firma.
P.S. Un programator cu experienta isi alege firma unde lucreza nu invers.

Edited by jm2010, 15 March 2013 - 10:17.

 reaper666, on 14 martie 2013 - 16:37, said:

Principalul considerent ar trebui să fie complexitatea algoritmului, sau mai simplu spus, efortul, numărul de paşi necesari pentru găsirea soluţiei. Nu e de neglijat nici estimarea resurselor necesare, poate una dintre abordări funcţionează cu resurse mult mai mici. Uneori ai cazuri în care un algoritm e mai rapid dar consumă mai multe resurse şi atunci trebuie să alegi ce preferi, să meargă mai repede sau să consume mai puţin.

Depinde şi de limbajul de programare, unele limbaje pot oferi facilităţi care să te facă să înclini în mod natural spre o soluţie sau alta.

Un exemplu bun este parcurgerea documentelor XML. Există metode care încarcă tot documentul în memorie şi poţi ajunge "manual" şi foarte rapid la orice nod dacă-i ştii locaţia ierarhică, face căutări etc. Dar consumă multă memorie. Sau poţi folosi metode care nu reţin nimic în memorie, se apelează recursiv pentru fiecare nod sau nivel ierarhic din structura XML, şi ca să găseşti un nod de un anumit tip sau anumită locaţie trebuie să "interceptezi" condiţional procesarea când ajunge la anumite puncte.

 TS030, on 14 martie 2013 - 22:19, said:

Depinde de modul în care gândeşti soluţia. Poţi spune "hai să înmulţim toate numerele între 1 şi n", sau poţi spune "n! = n x (n-1)!" Ambele sunt moduri perfect acceptabile de a vedea lucrurile.

 Pac_Man, on 14 martie 2013 - 16:58, said:

Poţi adăuga directoarele într-o listă şi să o parcurgi liniar. Începi cu lista conţinând doar directorul de start, iar fiecare iteraţie va consta din:
* afişarea fişierelor şi directoarelor din directorul aferent intrării curente
* inserarea directoarelor găsite în listă, imediat după intrarea curentă dar înainte de alte intrări
* avansare la următoarea intrare

Edited by wirespot, 15 March 2013 - 10:29.

 wirespot, on 15 martie 2013 - 10:23, said:

Da, dar este mai ineficient (cod redundant).

Edited by jm2010, 15 March 2013 - 10:28.

Ce anume este redundant în algoritm?

Este mai costisitor pentru că apar în plus operaţiuni de menţinere a listei şi inserarea în ea, de acord (presupunând că nu cumva costul de apelare al unei funcţii e mai mare sau echivalent).

Dar pe de altă parte nu mai sunt limitat pe adâncime de stivă ci de memoria principală, care-i mult mai mare. La un algoritm recursiv adâncimea maximă e deseori un punct vulnerabil.

Să zicem că ai un manager de fişiere şi vrei să oferi clientului o listare arborescentă sau o căutare pe numele fişierelor şi directoarelor. Vei prefera implementarea un pic mai rapidă dar care are şanse mai mari să crape la o anumită adâncime, sau una un pic mai lentă care e puţin probabil să dea de limitări de memorie?

Edited by wirespot, 15 March 2013 - 10:48.

 jm2010, on 15 martie 2013 - 08:43, said:

A fost un exemplu. Am subliniat ceea ce deja am spus mai sus. Atunci cand adancimea nu este limitata (sa o poti controla spre exemplu) atunci nu folosesti recursivitatea (asa cum am bold-uit mai sus). In functie de caz dar, daca poti folosi ambele variante (solutia iti permite), recursivitatea este mai eficienta (si iterativ, in afara cazului in care vrei sa pui tot codul in aceeasi metoda si astfel ai redundata - mai greu de intretinut - tot vei folosi apeluri de functii, deci nici viteza nu iti va fi influenta prea mult de iterativitate vs recursivitate).

P.S. Sunt solutii recursive si pentru cazul directoarelor. Sunt solutii sa eviti problema stack-ului in cazul afisarii directoarelor dintr-un sistem. Nu este chiar un exemplu relevant.

Edited by jm2010, 15 March 2013 - 10:53.

la viteza recursivul e mai slab, apelul acela de functie(saltul) e costisitor ca timp

singurul avantaj major pe care-l vad eu in recursivitate e diminuarea nr. de linii

dar nu e practică recursivitatea, daca scrii o functie recursiva si apoi(dupa o luna de exemplu) trebuie sa revii asupra ei sa o modifici e posibil sa dai de draq. pe cand una iterativa o modifici usor.

recursivitatea cere si mai multa intelegere. pt mine e un semn de pricepere daca reusesti sa transformi usor si eficient din iterativ in recursiv.

Edited by Dorin_78, 15 March 2013 - 11:10.

 Dorin_78, on 15 martie 2013 - 10:57, said:

Corect dar, asa cum spuneam, depinde de problema. In unele cazuri poate deveni costisitor in altele nu (nu ma refer aici o o metoda cu 5 linii in care doar se citeste o variabila ci la chestii serioase cum te intalnesti in practica).

Nu cred că e posibil să generalizezi şi să decizi că recursivitatea e mereu mai eficientă. Ce înseamnă "eficient" depinde de la caz la caz, de mulţi factori.

Quote

De folosit probabil poţi folosi orice abordare în orice problemă. Poţi forţa soluţii recursive sau iterative în cazuri în care cealaltă abordare ar fi fost mai naturală sau mai eficientă.

Dar ce e "natural" e subiectiv, ţine de limitele de experienţă şi imaginaţie şi flexibilitatea mentală a programatorului. Iar ce e "eficient" depinde de arhitectura sistemului, de limbaj, de resursele disponibile etc.