Funkcja rekurencyjna – funkcja która jest obliczalna za pomocą maszyny Turinga. Klasę tych funkcji definiuje się za pomocą mniejszej klasy funkcji pierwotnie rekurencyjnych:
Funkcja pierwotnie rekurencyjna Funkcjami pierwotnie rekurencyjnymi nazywamy funkcje: Funkcja zerowa zdefiniowana jako Funkcja następnika zdefiniowana jako Funkcja rzutowania zdefiniowana jako
oraz wszystkie funkcje zbudowane z funkcji pierwotnie rekurencyjnych za pomocą następujących metod kompozycji:
Złożenia funkcji Dla danych funkcji oraz złożeniem nazywamy funkcję zdefiniowaną jako
Rekursji prostej Dla danych funkcji oraz złożeniem rekurencyjnym nazywamy funkcję zdefiniowaną jako
Funkcja częściowo rekurencyjna Dodając do zbioru możliwych operacji operator minimalizacji otrzymujemy klasę funkcji częściowo rekurencyjnych: Operator minimalizacji
Dla danej funkcji definiujemy funkcję w ten sposób, że wartością jest minimalne y takie, że jest zdefiniowane, oraz
Ponieważ nie dla wszystkich wartości takie y musi istnieć, funkcje częściowe rekurencyjne mogą być (w przeciwieństwie do funkcji pierwotnie rekurencyjnych) funkcjami częściowymi.
Funkcja rekurencyjna Funkcję częściowo rekurencyjną, która jest zdefiniowana dla każdego argumentu, nazywamy funkcją rekurencyjną