Cuprins
- Cuprins pag. 2
- Cuvânt înainte pag. 3
- Cap. I Recursivitate pag. 4
- - Notiunea de algoritm recursiv
- - Exemple de algoritmi recursivi. Relatii de recurenta
- - Rolul stivei în executia subprogramelor recursive
- Cap. II Subprograme recursive - Functii recursive pag. 9
- - Exemplu n factorial ( n! )
- - Aplicatie
- - Aplicatie - Sirul lui Fibonacci
- - Aplicatie - Cel mai mare divizor comun
- - Aplicatie - Numarul elementelor negative într-un sir
- - Aplicatie - Suma cifrelor unui numar natural
- - Aplicatie - Combinari de n elemente luate câte k
- - Functii recursive
- Cap. III Program Calcul matematic – codul sursa pag. 26
Extras din proiect
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.
Preview document
Conținut arhivă zip
- Functii Recursive - Turbo Pascal
- Functii Recursive - Turbo Pascal.doc
- MATE.BAK
- MATE.PAS