Introducere în recursivitate
Î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.
Nu toate funcțiile matematice pot fi definite recursiv; cu alte cuvinte există și funcții nerecursive.
Definiţii formale ale recursiei
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:
Un alt exemplu ar fi definirea conceptului de strămoș al unei persoane: