Funcții recursive - Turbo Pascal

CUVÂNT ÎNAINTE

Acest proiect la informatica consta în prezentarea în limbajul de programare

Turbo Pascal a unei probleme ce îsi propune sa expuna cât mai multe dintre

cunostintele acumulate în timpul celor 4 ani de liceu.

Pe lânga notiunile de teorie ce vor face obiectul acestuia ( Recursivitate,

functii recursive si Backtracking ), explicarea aprofundata a tuturor pasilor

algoritmului, atasarea fisierului ce demonstreaza corectitudinea problemei, vor

încerca sa dovedeasca pregatirea cât mai temeinica a autoarei.

Capitolul I. RECURSIVITATE

a) Notiunea de algoritm recursiv.

Recursivitatea este una din notiunile fundamentale ale informaticii. Utilizarea frecventa a recursivitatii s-a facut dupa anii '80. Multe din limbajele de programare evoluate si mult utilizate (Fortran, Cobol ) nu permiteau scrierea programelor recursive.

In linii mari, recursivitatea este un mecanism general de elaborare a programelor. Ea a aparut din necesitati practice ( transcrierea directa a formulelor matematice recursive) si reprezinta acel mecanism prin care un subprogram ( procedura, functie ) se autoapeleaza.

Daca lucrurile par usor de înteles în cazul functiilor, nu tot atât de simplu este sa aplicam recursivitatea utilizând proceduri. Astfel vom vedea ca putem genera recursiv probleme de genul permutarilor.

Un algoritm recursiv se caracterizeaza prin proprietatea ca se auto-apeleaza, adica din interiorul lui se apeleaza pe el însusi. Din afara algoritmului facem un

prim apel al acestuia, dupa care algoritmul se auto-apeleaza de un anumit numar de ori; la fiecare noua auto-apelare a algoritmului, se executa din nou secventa de instructiuni ce

reprezinta corpul sau, eventual cu alte date, creându-se un asa-numit "lant de auto-apeluri recurstive".

Intuitiv, putem spune ca un algoritm recursiv are acelasi efect ca si un ciclu: repeta executia unei anumite secvente de instructiuni. Dar la fel ca în cazul unui ciclu, este necesar ca repetarea sa nu aiba loc la infinit. De aceea, în corpul algoritmului trebuie sa existe cel putin o testare a unei conditii de oprire, la îndeplinirea careia se întrerupe lantul de auto-apeluri. Majoritatea algoritmilor repetitivi se pot implementa atât în varianta nerecursivâ (care se mai numeste si iterativa ), folosind cicluri, cât si în varianta recursiva.

Ramâne în sarcina programatorului sa aleaga între implementarea iterativa si cea recursiva, cântarind avantajele si dezavantajele fiecareia, de la caz la caz.

Varianta recursiva este recomandata în special pentru

problemele definite prin relatii de recurenta, care permit o formulare a rezultatelor mult mai clara si mai concisa. Pe de alta parte, functionarea algoritmilor recursivi este în

general mai greu de urmarit, si, în plus, acestia necesita un timp de executie mai lung si un spatiu de memorie mai mare.

Extinzând definitia, vom numi subprogram recursiv (functie recursiva sau procedura recursiva ), un subprogram care din corpul lui se apeleaza pe el însusi. Dar orice subprogram recursiv trebuie sa îndeplineasca doua cerinte:

1. Sa se poata executa cel putin o data fara a se auto-apela:

2. Toate auto-apelurile sa se produca astfel încât sa se tinda spre îndeplinirea

conditiei de executie fara auto-apelare.