luni, 12 aprilie 2010

Recursivitatea

In informatica si in matematica, recursivitatea reprezinta un concept fundamental. Putem spune ca o notiune este definita recursiv daca in cadrul definitiei notiunii apare insasi notiunea care se defineste.
Un algoritm recursiv se caracterizeaza prin proprietatea ca se autoapeleaza.
Intuitiv, putem spune ca un algoritm recursiv are acelasi efect ca si un ciclu: repeta executia unei anumite secvente de instructiuni; de aceea in corpul algoritmului trebuie sa existe cel putin o testare a unei conditii de oprire, la indeplinirea careia se intrerupe lantul de autoapeluri.
Regulile fundamentale pentru ca recursivitatea sa fie definita corect sunt:
  existenta cazurilor elemetare, care se pot rezolva direct.
  pentru cazurile care nu se rezolva direct recursivitatea trebuie sa progreseze catre un caz elementar.