Recursiune sau bucle while (Inginerie software, Calitatea Codului, Recursivitate)

Shivan Dragon a intrebat.

Citeam despre niște practici de interviu de dezvoltare, mai exact despre întrebările și testele tehnice puse la interviuri și m-am împiedicat de destul de multe ori de ziceri de genul „Ok ai rezolvat problema cu un while loop, acum poți să o faci cu recursivitate”, sau „toată lumea poate rezolva asta cu un while loop de 100 de linii, dar poate să o facă într-o funcție recursivă de 5 linii?” etc.

Întrebarea mea este: este recursivitatea în general mai bună decât construcțiile if/while/for?

Sincer, întotdeauna am crezut că recursivitatea nu este de preferat, deoarece este limitată la memoria stivei care este mult mai mică decât heap-ul, de asemenea, efectuarea unui număr mare de apeluri de funcții/metode este suboptimală din punct de vedere al performanței, dar s-ar putea să mă înșel…

Comentarii

  • Poate doriți să citiți următoarele –  > Por Naftali aka Neal.
  • 79

  • În ceea ce privește subiectul recursivității, acest lucru pare destul de interesant. –  > Por dan_waterworth.
  • @dan_waterworth, de asemenea, acest lucru ar fi de ajutor: google.fr/… dar se pare că întotdeauna îl scriu greșit 😛 – –  > Por Shivan Dragon.
  • @ShivanDragon Așa mă gândeam și eu ^_^ Foarte potrivit că am postat-o ieri 🙂 –  > Por Naftali aka Neal.
  • În mediile embedded în care am lucrat eu, recursivitatea este în cel mai bun caz prost văzută și în cel mai rău caz te biciuiește public. Spațiul limitat al stivei o face, de fapt, ilegală. –  > Por Fred Thomsen.
8 răspunsuri
tdammers

Recursiunea nu este intrinsec mai bună sau mai rea decât buclele – fiecare are avantaje și dezavantaje, iar acestea depind chiar și de limbajul de programare (și de implementare).

Din punct de vedere tehnic, buclele iterative se potrivesc mai bine sistemelor informatice tipice la nivel hardware: la nivelul codului de mașină, o buclă este doar un test și un salt condițional, în timp ce recursivitatea (implementată naiv) implică împingerea unui cadru de stivă, sărituri, reveniri și reveniri din stivă. În schimb, multe cazuri de recursivitate (în special cele care sunt echivalente în mod trivial cu buclele iterative) pot fi scrise astfel încât să se evite împingerea / extragerea stivei; acest lucru este posibil atunci când apelul funcției recursive este ultimul lucru care se întâmplă în corpul funcției înainte de a se întoarce și este cunoscut în mod obișnuit sub denumirea de optimizare a apelului de coadă (sau tail recursion optimization (optimizare a recursivității de coadă)). O funcție recursivă optimizată corespunzător pentru apelul de coadă este în mare parte echivalentă cu o buclă iterativă la nivelul codului mașină.

Un alt aspect de luat în considerare este că buclele iterative necesită actualizări distructive ale stării, ceea ce le face incompatibile cu semantica pură a limbajului (fără efecte secundare). Acesta este motivul pentru care limbajele pure, cum ar fi Haskell, nu au deloc construcții de buclă, iar multe alte limbaje de programare funcțională fie nu le au deloc, fie le evită pe cât posibil.

Totuși, motivul pentru care aceste întrebări apar atât de des la interviuri este că, pentru a răspunde la ele, trebuie să înțelegeți temeinic multe concepte vitale de programare – variabile, apeluri de funcții, domeniu de aplicare și, bineînțeles, bucle și recursivitate – și trebuie să aduceți la masă flexibilitatea mentală care vă permite să abordați o problemă din două unghiuri radical diferite și să treceți de la o manifestare la alta a aceluiași concept.

Experiența și cercetarea sugerează că există o linie de demarcație între persoanele care au capacitatea de a înțelege variabilele, indicatorii și recursivitatea și cele care nu au această capacitate. Aproape tot restul în programare, inclusiv cadrele, API-urile, limbajele de programare și cazurile lor limită, pot fi dobândite prin studiu și experiență, dar dacă nu sunteți în măsură să dezvoltați o intuiție pentru aceste trei concepte de bază, nu sunteți apt să fiți programator. Traducerea unei bucle iterative simple într-o versiune recursivă este cam cea mai rapidă modalitate posibilă de a filtra neprogramatorii – chiar și un programator destul de neexperimentat o poate face, de obicei, în 15 minute, și este o problemă foarte agnostică față de limbaj, astfel încât candidatul poate alege un limbaj la alegere în loc să se împiedice de idiosincraziile sale.

Dacă primiți o astfel de întrebare la un interviu, este un semn bun: înseamnă că potențialul angajator caută persoane care știu să programeze, nu persoane care au memorat manualul unui instrument de programare.

Comentarii

  • Îmi place cel mai mult răspunsul tău,pentru că atinge cele mai importante aspecte pe care le-ar putea avea un răspuns la această întrebare,explică principalele părți tehnice,și oferă și o bună perspectivă zoom-out asupra modului în care această problemă se încadrează în sfera programării. –  > Por Shivan Dragon.
  • Am observat și eu un tipar într-o programare sincronizată în care buclele sunt evitate în favoarea apelurilor recursive pe un iterator care conține o metodă .next(). Presupun că acest lucru împiedică codul care rulează mult timp să devină prea lacom de CPU. –  > Por Evan Plaice.
  • Versiunea iterativă implică, de asemenea, împingerea și eliminarea valorilor. Trebuie doar să scrieți manual codul pentru a face acest lucru. Versiunea recursivă presupune împingerea stării pe stivă într-un algoritm iterativ. De obicei, trebuie să simulați manual acest lucru prin împingerea stării într-o anumită structură. Doar cei mai triviali algoritmi nu au nevoie de această stare și, în aceste cazuri, compilatorul poate, de obicei, să detecteze recursivitatea de coadă și să instaleze o soluție iterativă. –  > Por Martin York.
  • @tdammers Puteți să-mi spuneți unde pot citi studiul pe care l-ați menționat: „Experiența și cercetarea sugerează că există o linie de demarcație între oameni…” Acest lucru pare a fi foarte interesant pentru mine. –  > Por Yoo Matsuo.
  • Un lucru pe care ai uitat să-l menționezi, codul iterativ tinde să funcționeze mai bine atunci când ai de-a face cu un singur fir de execuție, dar algoritmii recursivi tind să se preteze la a fi executați în mai multe fire de execuție. –  > Por GordonM.
jk.

Depinde.

  • Unele probleme se pretează foarte bine la soluții recursive, de ex. quicksort
  • Unele limbaje nu suportă cu adevărat recursivitatea, de ex. primele FORTRAN-uri
  • Unele limbaje presupun recursivitatea ca mijloc principal pentru buclă, de ex. Haskell

De asemenea, merită menționat faptul că suportul pentru recursivitate de coadă face ca buclele recursive de coadă și cele iterative să fie echivalente, adică recursivitatea nu trebuie să irosească întotdeauna stiva.

De asemenea, un algoritm recursiv poate fi întotdeauna implementat iterativ prin utilizarea unei stive explicite.

În cele din urmă, aș remarca faptul că o soluție de cinci linii este probabil întotdeauna mai bună decât una de 100 de linii (presupunând că acestea sunt de fapt echivalente).

Comentarii

  • Frumos răspuns (+1). „o soluție pe 5 linii este probabil întotdeauna mai bună decât una pe 100 de linii”: Cred că concizia nu este singurul avantaj al recursivității. Folosirea unui apel recursiv vă obligă să faceți explicite dependențele funcționale dintre valorile din diferite iterații. –  > Por Giorgio.
  • Soluțiile mai scurte tind să fie mai bune, dar există un astfel de lucru ca să fii prea concis. –  > Por dan_waterworth.
  • @dan_waterworth în comparație cu „100 de rânduri” este destul de dificil să fii prea mult laconic –  > Por gnat.
  • @Giorgio, Poți face programele mai mici prin eliminarea codului inutil sau prin a face lucruri explicite implicite. Atâta timp cât te rezumi la primele, îmbunătățești calitatea. –  > Por dan_waterworth.
  • @jk, Cred că aceasta este o altă formă de a face implicite informațiile explicite. Informația despre scopul pentru care este folosită o variabilă este eliminată din numele ei, unde este explicită, și este împinsă în utilizarea ei, care este implicită. –  > Por dan_waterworth.
dan_waterworth

Nu există o definiție unanim acceptată a cuvântului „mai bun” atunci când vine vorba de programare, dar eu consider că înseamnă „mai ușor de întreținut/citit”.

Recursiunea are mai multă putere de expresie decât construcțiile iterative de buclă: Spun acest lucru deoarece o buclă while este echivalentă cu o funcție recursivă de coadă, iar funcțiile recursive nu trebuie să fie recursive de coadă. Construcțiile puternice sunt, de obicei, un lucru rău, deoarece vă permit să faceți lucruri care sunt greu de citit. Cu toate acestea, recursivitatea vă oferă posibilitatea de a scrie bucle fără a utiliza mutabilitatea și, după părerea mea, mutabilitatea este mult mai puternică decât recursivitatea.

Așadar, de la putere expresivă redusă la putere expresivă ridicată, construcțiile de buclă se prezintă astfel:

  • Funcții recursive de coadă care utilizează date imuabile,
  • funcții recursive care utilizează date imuabile,
  • bucle While care utilizează date mutabile,
  • funcții recursive de coadă care utilizează date mutabile,
  • funcții recursive care utilizează date mutabile,

În mod ideal, ar trebui să utilizați construcțiile cele mai puțin expresive pe care le puteți utiliza. Desigur, dacă limbajul dvs. nu acceptă optimizarea apelurilor de coadă, atunci acest lucru poate influența și alegerea construcției de buclă.

Comentarii

  • „o buclă while este echivalentă cu o funcție recursivă de coadă, iar funcțiile recursive nu trebuie să fie recursive de coadă”: +1. Puteți simula recursivitatea prin intermediul unei bucle while + o stivă. –  > Por Giorgio.
  • Nu sunt sigur că sunt de acord 100%, dar cu siguranță este o perspectivă interesantă, așa că +1 pentru asta. –  > Por Konrad Rudolph.
  • +1 pentru un răspuns excelent și, de asemenea, pentru că ați menționat că unele limbaje (sau compilatoare) nu fac optimizări de apelare a cozii. –  > Por Shivan Dragon.
  • @Giorgio, „Poți simula recursivitatea prin intermediul unei bucle while loop + o stivă”, De aceea am spus putere expresivă. Din punct de vedere computațional, sunt la fel de puternice. –  > Por dan_waterworth.
  • @dan_waterworth: Exact, și așa cum ați spus în răspunsul dumneavoastră, recursivitatea singură este mai expresivă decât o buclă while, deoarece trebuie să adăugați o stivă la o buclă while pentru a simula recursivitatea. –  > Por Giorgio.
SF.

Recursivitatea este adesea mai puțin evidentă. Mai puțin evidentă este mai greu de întreținut.

Dacă scrieți for(i=0;i<ITER_LIMIT;i++){somefunction(i);} în fluxul principal, este foarte clar că scrieți o buclă. Dacă scrieți somefunction(ITER_LIMIT); nu clarificați cu adevărat ce se va întâmpla. Vedeți doar conținutul: asta somefunction(int x) apelează somefunction(x-1) vă spune că este de fapt o buclă care folosește iterații. De asemenea, nu poți pune cu ușurință o condiție de scăpare cu break; undeva la jumătatea iterațiilor, trebuie fie să adăugați o condiționalitate care va fi transmisă până la capăt, fie să aruncați o excepție. (iar excepțiile adaugă din nou complexitate…)

În esență, dacă este o alegere evidentă între iterație și recursivitate, faceți lucrul intuitiv. Dacă iterația face treaba cu ușurință, economisirea a 2 linii rareori merită durerile de cap pe care le poate crea pe termen lung.

Desigur, dacă economisești 98 de rânduri, este o cu totul altă problemă.

Există situații pentru care recursivitatea se potrivește pur și simplu perfect, iar acestea nu sunt chiar neobișnuite. Traversarea structurilor arborescente, rețelele cu legături multiple, structurile care pot conține propriul tip, matricele multidimensionale zimțate, în esență, tot ceea ce nu este fie un vector direct, fie o matrice de dimensiuni fixe. Dacă parcurgeți un traseu cunoscut și drept, iterați. Dacă vă scufundați în necunoscut, recurgeți.

În esență, dacă somefunction(x-1) trebuie să fie apelat din interiorul său mai mult de o dată pe nivel, uitați de iterații.

…Scrierea funcțiilor iterative pentru sarcini care se realizează cel mai bine prin recursivitate este posibilă, dar nu este plăcută. Oriunde ați folosi int, aveți nevoie de ceva de genul stack<int>. Am făcut-o o dată, mai mult ca exercițiu decât în scopuri practice. Te asigur că odată ce te vei confrunta cu o astfel de sarcină nu vei mai avea îndoieli ca cele exprimate de tine.

Comentarii

  • Ceea ce este evident și ceea ce este mai puțin evident depinde parțial de ceea ce ești obișnuit. Iterarea a fost folosită mai des în limbajele de programare pentru că este mai aproape de modul de lucru al procesorului (adică folosește mai puțină memorie și se execută mai repede). Dar dacă sunteți obișnuit să gândiți inductiv, recursivitatea poate fi la fel de intuitivă. –  > Por Giorgio.
  • „Dacă văd un cuvânt cheie de buclă, știu că este o buclă. Dar nu există un cuvânt cheie recurse, ei o pot recunoaște doar văzând f(x-1) în interiorul lui f(x).”: Atunci când apelați o funcție recursivă, nu doriți să știți că este recursivă. În mod similar, atunci când apelați o funcție care conține o buclă, nu doriți să știți că aceasta conține o buclă. –  > Por Giorgio.
  • @SF: Da, dar puteți vedea acest lucru doar dacă vă uitați la corpul funcției. În cazul unei bucle, vedeți bucla, în cazul recursivității, vedeți că funcția se apelează singură. –  > Por Giorgio.
  • @SF: Mie mi se pare un pic ca un raționament circular: „Dacă în intuiția mea este o buclă, atunci este o buclă.” map poate fi definită ca o funcție recursivă (a se vedea, de ex. haskell.org/tutorial/functions.html), chiar dacă intuitiv este clar că traversează o listă și aplică o funcție fiecărui membru al listei. –  > Por Giorgio.
  • @SF, map nu este un cuvânt cheie, ci o funcție obișnuită, dar asta este puțin irelevant. Atunci când programatorii funcționali folosesc recursivitatea, de obicei nu o fac pentru că vor să execute o secvență de acțiuni, ci pentru că problema care se rezolvă poate fi exprimată ca o funcție și o listă de argumente. Problema poate fi apoi redusă la o altă funcție și o altă listă de argumente. În cele din urmă, se obține o problemă care poate fi rezolvată în mod trivial. –  > Por dan_waterworth.
Kilian Foth

Ca de obicei, acest lucru este fără răspuns în general, deoarece există factori suplimentari, care, în practică, sunt foarte inegali între cazuri și inegali între ei în cadrul unui caz de utilizare. Iată câteva dintre presiuni.

  • Codul scurt și elegant este, în general, superior codului lung și complicat.
  • Cu toate acestea, ultimul punct este oarecum invalidat dacă baza dumneavoastră de dezvoltatori nu este familiarizată cu recursivitatea și nu dorește/nu poate să învețe. Ar putea chiar să devină o ușoară negativă mai degrabă decât un aspect pozitiv.
  • Recursivitatea poate fi negativă pentru eficiență dacă aveți nevoie în practică de apeluri adânc îmbinate și nu puteți utiliza recursivitatea de coadă (sau mediul dumneavoastră nu poate optimiza recursivitatea de coadă).
  • Recursivitatea este, de asemenea, negativă în multe cazuri dacă nu puteți pune în cache în mod corespunzător rezultatele intermediare. De exemplu, exemplul obișnuit de utilizare a recursivității arborelui pentru a calcula numerele Fibonacci are următoarele rezultate groaznic rău dacă nu se utilizează memoria cache. Dacă se utilizează memoria cache, este simplu, rapid, elegant și, în general, minunat.
  • Recursivitatea nu se aplică în unele cazuri, este la fel de bună ca iterația în altele și absolut necesară în altele. Parcurgerea unor lanțuri lungi de reguli de afaceri nu este, de obicei, deloc ajutată de recursivitate. Iterarea prin fluxuri de date poate fi realizată în mod util cu recursivitate. Iterarea peste structuri de date dinamice multidimensionale (de exemplu, labirinturi, arbori de obiecte…) este aproape imposibilă fără recursivitate, explicită sau implicită. Rețineți că, în aceste cazuri, recursivitatea explicită este mult mai mult mai bună decât cea implicită – nimic nu este mai dureros decât să citești cod în care cineva și-a implementat propria stivă ad-hoc, incompletă și plină de erori în cadrul limbajului doar pentru a evita înfricoșătorul cuvânt R.

Comentarii

  • Ce înțelegeți prin „caching” în legătură cu recursivitatea? –  > Por Giorgio.
  • @Giorgio se presupune că memoizarea –  > Por jk..
  • Feh. Dacă mediul dvs. nu optimizează apelurile de coadă, ar trebui să găsiți un mediu mai bun, iar dacă dezvoltatorii dvs. nu sunt familiarizați cu recursivitatea, ar trebui să găsiți dezvoltatori mai buni. Aveți niște standarde, oameni buni! –  > Por C. A. McCann.
okobaka

Recursiunea este despre apelarea repetată a unei funcții, bucla este despre repetarea salturilor la un loc în memorie.

Ar trebui să se menționeze, de asemenea, despre stack overflow – http://en.wikipedia.org/wiki/Stack_overflow

Comentarii

  • Recursiunea înseamnă o funcție a cărei definiție presupune apelarea ei însăși. –  > Por hardmath.
  • Deși definiția dvs. simplă nu este chiar 100% exactă, sunteți singurul care a menționat stack overflow-urile. –  > Por Qix – MONICA A FOST NEAȘTEPTATĂ.
neotam

Depinde într-adevăr de comoditate sau de cerință:

Dacă luați limbajul de programare Python, acesta suportă recursivitatea, dar în mod implicit există o limită pentru adâncimea de recursivitate (1000). Dacă se depășește limita, vom primi o eroare sau o excepție. Limita respectivă poate fi schimbată, dar dacă facem acest lucru putem avea situații anormale în limbaj.

În acest moment (număr de apeluri mai mare decât adâncimea de recursivitate), trebuie să preferăm construcțiile de tip buclă. Adică, dacă dimensiunea stivei nu este suficientă, trebuie să preferăm construcțiile de tip buclă.

Comentarii

  • Aici este un blog al lui Guido van Rossum cu privire la motivul pentru care nu dorește optimizarea recursiunii de coadă în Python (susținând ideea că diferite limbaje adoptă abordări tactice distincte). –  > Por hardmath.
Pravin Sonawane

Utilizați modelul de proiectare a strategiei.

  • Recursiunea este curată
  • Buclele sunt (fără îndoială) eficiente

În funcție de sarcina dvs. (și/sau alte condiții), alegeți una.

Comentarii

  • Stați, ce? Cum se potrivește modelul de strategie aici? Și a doua propoziție sună ca o frază goală. –  > Por Konrad Rudolph.
  • @KonradRudolph Eu aș opta pentru recursivitate. Pentru seturi foarte mari de date, aș trece la bucle. Asta am vrut să spun. Îmi cer scuze dacă nu a fost clar. –  > Por Pravin Sonawane.
  • Ah. Ei bine, încă nu sunt sigur că acest lucru poate fi numit „model de proiectare a strategiei”, care are un sens foarte fix și pe care îl folosiți metaforic. Dar acum cel puțin înțeleg unde vrei să ajungi. –  > Por Konrad Rudolph.
  • @KonradRudolph a învățat o lecție importantă. Explică în profunzime ceea ce vrei să spui… Mulțumesc… asta m-a ajutat… 🙂 –  > Por Pravin Sonawane.
  • @Pravin Sonawane: Dacă puteți utiliza optimizarea recursivității cozii, puteți utiliza recursivitatea și pe seturi de date uriașe. –  > Por Giorgio.