Rekursijos teorema skaičiavimo sudėtingumo teorijoje yra pagrindinė sąvoka, leidžianti gauti programos aprašymą pačioje programoje. Ši teorema vaidina svarbų vaidmenį suprantant skaičiavimo ribas ir tam tikrų skaičiavimo problemų sprendimo sudėtingumą. Norint suvokti rekursijos teoremos reikšmę, tai yra