Teorie Recursivitate

Definitie
Spunem ca o notiune este definita recursiv daca in definitia ei apare insa si notiunea care se defineste.
In informatica numim recursivitatea directa, proprietatea functiilor de a se autoopera.

Observatii
1) Orice f recursiva trebuie sa contina o conditie de oprire,respectiv de continuare.
2)la fiecare apel al f. se executa aceasi secventa de instructiuni.
3)tinand seama de observatia anterioara pentru a scrie un program recursiv problema trebuie sa contina o functie care sa contina relatia de recurenta
4)la fiecare apel in zona de stiva a memoriei se creeaza un nivel sau pe stiva se memoreaza val parametrilor formali transmisi prin valoare, adresa param. formali transmisi prin referinta, adresa de revenire, variabilele locale cu val din mom respectiv.
5)toate instructiunile din subprogram se executa pentru fiecare reapel.

Când folosim recursivitatea
-Ce-a de-a doua definitie a lui n! este exprimata printr-o formula de recurenta: n!=n*(n-1)!. În ciuda numelui sau, o relatie de recurenta poate fi implementata recursiv sau iterativ. Desi solutiile iterative se executa mult mai eficient decât unele recursive, ele sunt adesea prea dificil de codificat. Eficienta unei rutine recursive este în mare masura dependenta de faptul ca ea repeta o parte din munca depusa pentru a obtine raspunsul final. La nici unul din exemplele anterioare nu am înâlnit acest lucru. Functia factoriala recursiva de exemplu, are nevoie de 4! pentru a calcula 5!, dar 4! se calculeaza numai o singura data. Dar, cu siguranta alte rutine, daca sunt scrise recursiv ar repeta o parte din... truda lor de mai multe ori!
-Consideram în cele ce urmeaza celebrul sir al lui Fibonacci (matematician italian, secolul XIII), în care fiecare termen dupa 0 si 1 este obtinut din suma celor doi termeni precedenti.
F(0)=0, F(1)=1, … , F(n)=F(n-1)+F(n-2)
F(0) F(1) F(2) F(3) F(4) F(5) F(6) F(7)…
0 1 1 2 3 5 8 13…
Asa cum l-am scris noi, ca o secventa de-a lungul paginii, procedam iterativ; fiecare numar este calculat o singura data.

În informatică, recursivitatea sau recursia este un mod de a defini unele funcţii. Funcţia este recursivă, dacă definiţia ei foloseşte o referire la ea însăşi, creând la prima vedere un cerc vicios, care însă este numai aparent, nu şi real.
Recursivitatea funcţionează prin definirea unuia sau a mai multe cazuri de bază, foarte simple, şi apoi prin definirea unor reguli prin care cazurile mai complexe se reduc la cazuri mai simple.
Un exemplu de recursivitate este în definirea formală a numerelor naturale din cadrul teoriei mulţimilor:
* baza recursiei este faptul că 1 este număr natural;
* în plus, orice număr natural are un succesor, care este de asemenea un număr natural.
Un alt exemplu ar fi definirea conceptului de strămoş al unei persoane:
* Un părinte este strămoşul copilului. ("Baza"')
* Părinţii unui strămoş sunt şi ei strămoşi ("Pasul de recursie").