Teoria rekursji – dział logiki matematycznej, którego początki sięgają lat trzydziestych XX wieku. Do jego powstania i rozwoju w znacznym stopniu przyczynili się między innymi Alan Turing i Stephen Cole Kleene.
Teoria rekursji zaczyna od badania obiektów (na przykład funkcji, relacji czy zbiorów), które nazywa się rekurencyjnymi. Funkcje rekurencyjne to takie funkcje o argumentach i wartościach należących do zbioru liczb naturalnych, które albo są szczególnie prostej postaci (jak funkcja stała czy funkcja identycznościowa), albo powstają z tych pierwszych w wyniku zastosowania skończonej liczby „porządnych” operacji (takich jak składanie funkcji czy definiowanie rekurencyjne). Natomiast zbiór jest rekurencyjny, gdy jego funkcja charakterystyczna jest rekurencyjna. Funkcje rekurencyjne są modelem (w sensie nieformalnym) funkcji czy relacji „obliczalnych”, to znaczy takich których wartość dla dowolnych argumentów można podać w skończonej liczbie kroków w sposób mechaniczny.