Algoritmi recursivi vs iterativi

 OriginalCopy, on 16 martie 2013 - 15:13, said:

Vorbesti de un caz particular, in care varianta recursiva e usor de inteles si una iterativa nu? Caci codul iterativ nu este in mod necesar dificil de inteles.
Cu abordarea sunt de acord, optimizarile "la sange" nu le faci doar ca ti se pare tie c-ar fi fain; trebuie sa stii ce sa optimizezi. As avea doua precizari suplimentare:
- e bine sa eviti din start solutiile clar ineficiente, asta daca nu cumva ai un motiv anume. Nu vorbesc de optimizari costisitoare, ci chestii de genul "ce sens are sa calculez recursiv un factorial", sau "de ce tot realoc memorie in rutina asta care e mereu apelata, cand se poate si altfel".
- chiar cand optimizezi un algoritm, e bine sa incerci sa scrii cod clar, cat mai usor de inteles.

Mai mereu, atunci când datele problemei sunt izomorfe, şi soluţia cea mai rapid de implementat şi de înţeles e cea recursivă. La alte probleme nici nu are rost să îţi pui problema din titlul topicului, mergi cu cea naturală pentru problema respectivă, iterativă.

Cu codul clar, mic, compact, şi evident corect deoarece l-ai făcut "ca din manual", scris în faţa ta, scrii testele, dacă nu le-ai scris înainte ca în TDD, măcar le scrii după, ca-n TAD.

Şi mergi mai departe la alte părţi ale codului. Că programul doar n-o fi făcut doar din acel algoritm. Ai un deadline, nu stai de abureli algoritmiceşti.

Apoi, când treci la profiling, începi să te uiţi pe cifre, şi să optimizezi dacă se impune. Fără profiling, singurul lucru ineficient este pierderea timpului cu întrebări "e mai bine aşa sau invers?". E fix pix, e inginerie, fără cifre nu există răspunsuri.

Summa summarum: oricare ar fi problema şi preferinţele, mai întâi scrii soluţia pe care o poţi implementa 100% corect, fără să transpiri, şi în timp util.

In practica, rareori a trebuit sa rezolv o problema care implica recursivitate. Problema (pentru un incepator, desigur) e sa recunosti cand trebuie sa o faci, si sa stii cum.
Bine spui. Pentru toate trebuie sa existe un motiv, iar optimizarile intensive nu fac exceptie. OK, daca alegi un algoritm ineficient cand unul mai bun iti era la indemana, iti iei palme dupa ceafa; dar si daca stai o saptamana optimizand ce nu trebuie, tot la fel o sa patesti. Sau daca "optimizarile", in mod nejustificat, dauneaza claritatii codului.

Implementarea aia in Haskell numai in place nu e, deci comparatia nu tine.
Adica ala din C consuma O(N) memorie, ala din Haskell pare sa consuma O( N + N*log(n) ) memorie.

Intre o solutie iterativa si una recursiva e de de preferat aia iterativa atunci cand e suficient de usor de scris ( in general o sa faci economie la memorie si o sa fie si mai usor de inteles ).

@trident, nu neapărat. Limbajele funcţionale nu lucrează cu memoria în modul "clasic". Nu se alocă manual date, multe nici măcar nu au operator de assign de variabile.

Termenul oficial este lazy evaluation. O să dau un citat din "Why functional programming matters" care explică acest aspect (unde "program" poate fi substituit cu "funcţie", "metodă" etc.):

Quote

Probabil cea mai cunoscută implementare practică a acestui principiu este operatorul pipe (|) din interfeţele cu linie de comandă.

Editat de wirespot, 17 martie 2013 - 14:47.