Algoritm recursiv

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Notă despre dezambiguizare.svg Dezambiguizare - "Recursivitate" se referă aici. Dacă sunteți în căutarea recursivității într-un domeniu lingvistic, consultați Recursiunea (lingvistică) .
Fără surse!
Această intrare sau secțiune despre programare nu citează sursele necesare sau cei prezenți sunt insuficienți .
Puteți îmbunătăți această intrare adăugând citate din surse de încredere în conformitate cu liniile directoare privind utilizarea surselor .
Triunghiul Sierpiński

În informatică, un algoritm recursiv este un algoritm exprimat în termeni în sine, adică în care execuția algoritmului pe un set de date implică simplificarea sau subdivizarea setului de date și aplicarea aceluiași algoritm la seturile de date simplificate .

Această tehnică este utilă în special pentru efectuarea de sarcini repetitive pe un set de variabile de intrare . Algoritmul se numește singur generând o secvență de apeluri care se termină atunci când apare o anumită condiție care se numește o condiție de terminare , care apare în general cu anumite valori de intrare .

Tehnica recursivă vă permite să scrieți algoritmi eleganți și sintetici pentru multe tipuri de probleme comune, chiar dacă soluțiile recursive nu sunt întotdeauna cele mai eficiente. Acest lucru se datorează faptului că recursivitatea este implementată în mod obișnuit folosind funcții și că invocarea unei funcții are un cost semnificativ și acest lucru face algoritmii iterativi mai eficienți.

În unele cazuri, recursivitatea este la fel de eficientă ca o buclă iterativă : limbajele paradigmelor funcționale sau logice nu au de obicei conceptul de buclă și folosesc recursivitatea prin optimizarea automată ( optimizarea apelurilor de la coadă ).

Un exemplu: factorialul unui număr

Pentru a înțelege conceptul vom folosi un exemplu matematic, calculul factorialului unui număr n . Un alt exemplu simplu ar fi putut fi cel al secvenței Fibonacci .

Vom numi factorial de n și vom scrie n! , produsul primelor n numere naturale , obținut după cum urmează:

 0! = 1; Pentru definire
         1! = 1;
         n! = 1 * 2 * 3 * ...... * n-1 * n; pentru n> 0.

Reelaborând definiția, ne dăm seama cum este posibil să îi oferim o versiune recursivă. În această privință:

 n! = (1 * 2 * 3 * ...... * n-1) * n;

primesti,

 n! = (n-1)! * n;

din care, iterând,

 n! = (n-2)! * (n-1) * n,

continuând să iterăm definiția, vom ajunge la condițiile de reziliere, pentru care este cunoscut rezultatul căutat:

 0! = 1! = 1.

Acum putem oferi un algoritm recursiv pe care îl vom numi FATT , pentru calculul factorialului. Rețineți că notația utilizată face distincție între simbolul x == y , pentru a indica egalitatea dintre cele două valori și simbolul x = y , pentru a indica că variabilei x i se va atribui valoarea y , precum și pentru C limba:

 int FATT (int n)
      {
         dacă (n <= 1) returnează 1;
         altfel returnează n * FACT (n-1);
      }

Când algoritmul este rulat pentru prima dată, valoarea lui n este comparată cu 0 și cu 1, dacă valoarea este diferită, procedura este apelată recursiv pe valori mai mici până când n este egal cu 1, caz în care rezultatul este cunoscut și poate fi returnat de la funcția curentă la cea care o numise anterior. Rezultatele returnate de fiecare dintre procedurile recursive sunt multiplicate din când în când. Penultima valoare returnată va fi exact egală cu (n-1)!, Aceasta din urmă va fi înmulțită cu n și algoritmul va putea returna rezultatul căutat.

În scopuri explicative și didactice, un algoritm pentru calcularea factorialului este furnizat mai jos, care utilizează o abordare iterativă :

 int FACT iterativ (int n)
      {
         int fatt = 1;
         while (1 <= n)
         {
            fatt = fapt * n;  
            n -;   
         }
         returnarea facturii;
      }

Tipuri de recursivitate

Există diferite tipuri de recursivitate. Vorbim de recursivitate reciprocă atunci când în algoritm o funcție numește alta care la rândul său o numește prima, altfel vorbim de recursivitate directă.

O altă distincție este aceea dintre recursivitatea liniară, care apare atunci când există doar un singur apel recursiv în cadrul funcției și neliniar dacă există mai multe apeluri recursive.

Cea mai importantă distincție în scopuri practice este între recursivitatea cozii și recursivitatea non-coadă. Vorbim de recursivitate de coadă atunci când apelul recursiv este ultima instrucțiune executată în funcție. Este posibil să se transforme o funcție care utilizează acest tip de algoritm recursiv într-o funcție iterativă, care este de obicei mai eficientă, deoarece nu este necesar să se mențină starea funcției odată ce a fost calculată așa cum sa făcut în exemplul anterior. Dacă algoritmul nu este recursiv în coadă, trebuie utilizat un mecanism de menținere a stării similar cu cel utilizat implicit în apelurile de funcții pentru a-l transforma într-o versiune iterativă.

Expresivitatea recursivității

Recursivitatea și iterația au aceeași expresivitate: recursiunea poate fi înlocuită prin iterație prin utilizarea unei stive explicite, în timp ce iterația poate fi înlocuită cu recursivitatea cozii. Cea mai bună abordare depinde de problema de rezolvat și de limbajul utilizat. În cazul limbajelor imperative, este preferată utilizarea iterației, în special în cazul recursivității liniare, deoarece evită cheltuielile cu apelurile funcționale și gestionarea stivei , în timp ce în limbajele funcționale, dimpotrivă, este preferată utilizarea recursiunii. , unde versiunea tail este adesea optimizată cu performanțe comparabile cu iterația.

Avantaje și dezavantaje

Recursivitatea are un avantaj fundamental: vă permite să scrieți câteva linii de cod pentru a rezolva chiar și o problemă foarte complexă. Cu toate acestea, are și un dezavantaj imens: performanța.

De fapt, recursivitatea generează o cantitate mare de cheltuieli generale , ocupând stiva pentru un număr de instanțe egal cu apelurile de funcții care trebuie făcute pentru a rezolva problema. Funcțiile care ocupă o cantitate mare de spațiu de memorie, chiar dacă pot fi implementate recursiv, ar putea da probleme de timp de execuție . De asemenea, recursivitatea necesită procesorului mai mult pentru a popula și distruge stive.

Prin urmare, dacă performanța este obiectivul principal al programului și nu aveți suficientă memorie, vă recomandăm să nu utilizați recursivitatea.

Principalele aplicații

Eliminarea recursivității

S-au făcut studii ample cu privire la modul de optimizare a codului unor rutine în care sarcina de memorie de alocare a funcției este prea mare. Se efectuează studii asupra naturii funcției și eliminarea recursivității se obține pentru o optimizare a memoriei.

Recursivitatea cozii

Recursivitatea de coadă apare atunci când, într-o procedură și / sau o funcție recursivă (care se numește singură), apelul recursiv este făcut ca ultim pas. Aceasta implică faptul că la întoarcerea de la apelul recursiv, funcția nu produce alți pași. Prin derularea recursiunii, putem înțelege modul în care această condiție poate fi optimizată prin înlocuirea unei funcții recursive cu una iterativă, care implică mai puțină complexitate spațială. Trecerea de la funcția recursivă la funcția iterativă poate fi efectuată pur și simplu prin reproducerea întregului corp al funcției în pași succesivi.

 nul F (x)
 {
  dacă P (x) atunci {D;}
  altceva 
  {
    ȘI; y = g (x); F (y);
  }
 }

Observați cum apelul recursiv este ultima afirmație a funcției. Prin urmare, poate fi ușor eliminat prin înlocuirea acestuia cu un construct iterativ

 nul F_it (x)
 { 
   în timp ce (P (x) == 0) atunci
     {ȘI; x = g (x);}
   {D;}
 }

Luați în considerare procedura de căutare binară (recursivă) într-un vector ordonat

 int binsearch (int a [], int sx, int dx, int el)
 { 
  int x;
  if (dreapta <stânga) returnează -1;
  x = (dreapta + stânga) / 2;
  if (el <a [x]) returnează căutare bins (a, sx, x-1, el);
  else if (el == a [x]) returnează x;
  altfel returnează binsearch (a, x + 1, dx, el);
 }

Observăm că apelurile recursive sunt executate ca ultimele instrucțiuni ale funcției. Dezvoltăm o versiune iterativă pentru căutare binară

 int binsearch_it (int a [], int dim, int el)
 { 
     int stânga, dreapta, x;
     sx = 0; dx = dim - 1;
     while (dreapta> = stânga)
     { 
        x = (dreapta + stânga) / 2;
        if (el == a [x]) returnează x;
        if (el <a [x]) dx = x - 1;
        else sx = x + 1;
     }
     retur -1;
 }

Recursivitate fără coadă

Când, pe de altă parte, recursivitatea nu este ultima instrucțiune a procedurii (recursivitate fără coadă), puteți opta pentru o soluție care implică utilizarea unei stive de suport care vă permite să salvați valorile apelurilor recursive și simulați într-o buclă de timp complet banală ce face stiva de sistem.

Curiozitate

Algoritmul recursiv este protagonistul cărții Crypto a scriitorului Dan Brown .

Soluția jocului creierului cunoscut sub numele de Turnul din Hanoi este ușor descrisă printr-un algoritm recursiv.

Recursivitatea poate fi, de asemenea, înțeleasă ca o versiune constructivă a principiului inducției , unde termenul „constructiv” indică capacitatea de a construi soluția unei probleme .

O propoziție faimoasă (raportată în Programarea recursivității de L. Peter Deutsch , dedicată în totalitate recursivității) spune că: To Iterate is Human, to Recurse, Divin („iterarea este umană, folosirea recursiunii este divină”).

Elemente conexe

Adus de la „ https://it.wikipedia.org/w/index.php?title=Recursive_Algorithm&oldid=121330664 ”