Conceptul de recursivitate

Conceptul de recursivitate

în informatică și matematică, recursivitatea este un concept fundamental. Spunem ca o noțiune este definită recursiv dacă în cadrul definiției intervine însăși noțiunea care se definește. De exemplu, un descendent al unei persoane este un copil al său sau un descendent al unui copil al său. În acest caz, pentru a defini noțiunea de descendent am folosit noțiunea însăși.

În matematică apar frecvent relații recursive, denumite și relații de recurență. De exemplu, să considerăm șirul Fibonacci : 0,1,1,2,3,5,8,13,21, …

Observăm că în acest șir primii doi termeni sunt 0 și 1, iar in rest, fiecare termen se obține însumând cei doi termeni care il preced. Prin urmare, o definiție recursivă pentru șirul Fibonaci este :

sirul finobacci

Apare înrebarea : orice descriere de acest tip este corect? Să consideram următorul exemplu :

exemplu sir finobacii

Observati că f (0)=1, iar dacă n>1, pentru a calcula f(n) trebuie sa evaluăm mai întâi f(n+1). Dar pentru a evalua f(n+1) va fi nevoie de f(n+2), deoarece n>0 impălică n+1>0 . Prin urmare, funcția f nu poate fi evaluată decât pentru 0.

Regulile fundamentale pentru recursivitatea să fie definită corect sunt:

  1. trebuie să existe cazuri elementare, care se pot rezolva direct,
  2. pentru cazurile care nu se rezolvă direct, recursivitatea trebuie să progreseze către un caz elementar.

Exemplu precedent încalcă a doua parte a acestei reguli.

O greșeală care apare frecvent este însă și încălcarea primei reguli. De exemplu, am solicitat unui elev să descrie o funcție recursivă care să calculeze suma cifrelor unui număr natural. Am abordat problema excelent : suma cifrelor unui număr natural n se obține adunând ultima cifră a numărului n(n%10) cu suma cifrelor numărului natural, care se obține eliminând ultima cifra din n(sum (n / 10)) și a scris relația următoare:

IMG_0182

Evident, a uitat cazurile elementare. Ca urmare, recursia nu se oprește niciodată : pentru a calcula suma cifrelor numărului natural, se elimină succesiv cifrele sale, până când argumentul n devine 0. Din acest moment, se evaluează la infinit sum(0), deoarece 0/10 este permanent 0.

Deci corect ar fi fost:

sir corect