Obiekty rekurencyjne można też zdefiniować w pozornie inny (lecz tak naprawdę równoważny) sposób. Mianowicie podzbiór A zbioru liczb naturalnych nazywamy rekurencyjnym, jeśli istnieje algorytm rozstrzygający dla każdej liczby naturalnej czy należy ona do zbioru A, czy nie. Określone w ten sposób pojęcie zbioru rekurencyjnego nie tylko jest identyczne z podanym powyżej, lecz nawet nie zależy od tego, jaki model obliczeń (przykłady zobacz w: funkcja rekurencyjna, teoria obliczeń, teoria obliczalności) wybierzemy do wykonywania algorytmów. Równoważność wszystkich „sensownych” modeli obliczeń jest postulowana w tezie Churcha, według której to czy zbiór (funkcja, relacja) jest obliczalny, czy też nie, nie zależy od wyboru modelu obliczeń.
Po obiektach rekurencyjnych następny stopień złożoności prezentują obiekty rekurencyjnie przeliczalne. Jeśli relacja R(m(1),...,m(k),n(1),...,n(l)) jest rekurencyjna, to relacja „istnieją takie m(1),...,m(k), że R(m(1),...,m(k),n(1),...,n(l))” jest rekurencyjnie przeliczalna. Dodając w definicji relacji kolejne kwantyfikatory ogólne i egzystencjalne w sposób naprzemienny, uzyskujemy nowe relacje, które mają (a w każdym razie mogą mieć) coraz większy stopień złożoności.