W ten sposób powstaje cała hierarchia obiektów, nazywana hierarchią arytmetyczną, której „piętra” można ponumerować liczbami naturalnymi.
Następnym krokiem jest dalsze komplikowanie rozważanych obiektów, które skutkuje przedłużeniem hierarchii arytmetycznej do jeszcze ogólniejszej hierarchii analitycznej. Teoria rekursji zajmuje się konstrukcją i szczegółowym badaniem tego typu hierarchii oraz szukaniem odpowiedzi na pytania w rodzaju: „jak skomplikowany jest dany zbiór (relacja, funkcja)?”, „na którym piętrze w badanej hierarchii można go umieścić?”, „na jakim poziomie stabilizuje się dana hierarchia?”. Pytania te, jakkolwiek łatwe do formułowania, okazują się często bardzo trudne. Teoria rekursji we współczesnym stanie jest wysoce abstrakcyjną dziedziną, którą zajmuje się stosunkowo niewielka liczba badaczy.
Związek z informatyką Na gruncie teorii rekursji powstała w drugiej połowie XX wieku teoria obliczeń, która stanowi obecnie ważny dział informatyki teoretycznej. Na pewnych wynikach tej teorii oparte zostały m.in.