Recursivitate

De la Wikipedia, enciclopedia liberă

Această pagină necesită categorisire. Pagina este insuficient categorisită sau nu a fost inclusă în nicio categorie tematică.

În matematică şi 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.

Nu toate funcţiile matematice pot fi definite recursiv; cu alte cuvinte există şi funcţii nerecursive.

[modifică] Definiţii formale ale recursiei

În matematică şi informatică 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").

[modifică] Vezi şi

[modifică] Legături externe