Algoritmi specifici şirurilor recurente

Un algoritm recursiv se caracterizează prin proprietatea că se autoapelează.Din afara algoritmului facem un prim apel al acestuia,după care algoritmul se auto-apelează de un anumit număr de ori:la fiecare nouă auto-apelare a algoritmului,se execută din nou secvenţa de instrucţiuni ce reprezintă corpul sau,eventual cu alte date,creându-se un aşa-numit lanţ de auto-apeluri recursive.

Intuitiv,putem spune că un algoritm recursiv are acelaşi efect ca şi un ciclu:repetă execuţia unei anumite secvenţe de instrucţiuni.Dar,la fel ca în cazul unui ciclu,este necesar ca repetarea să nu aibă loc la infinit.De aceea,în corpul algoritmului trebuie să existe cel puţin o testare a unei condiţii de oprire,la indeplinirea căreia se întrerupe lanţul de auto-apeluri.

Majoritatea algoritmilor repetitivi se pot implementa atât în varianta nerecursivă(care se mai numeşte şi iterativă),folosind cicluri,cât şi în varianta recursivă.Rămâne în sarcina programatorului să aleagă între implementarea iterativă si cea recursivă,cântărind avantajele şi dezavantajele,de la caz la caz.Varianta recursivă este recomandată în special pentru problemele definite prin relaţii de recurenţă,care permit o formulare a rezultatelor mult mai clară şi mai concisă.Pe de altă parte,funcţionarea algoritmilor recursivi este in general mai greu de urmărit,şi,in plus,aceştia necesită un timp de execuţie mai lung şi un spaţiu de memorie mai mare.

Extinzând definiţia,vom numi subprogram recursiv(procedură recursivă sau funcţie recursivă),un subprogram care din corpul lui se apelează pe el însuşi.Orice program recursiv trebuie să indeplinească două cerinţe:să se poată executa cel puţin o data fără a se auto-apela şi toate apelurile să se producă astfel încat să se tindă spre îndeplinirea condiţiei de execuţie fără auto-apelare.