rekursỹviosios fùnkcijos (lot. recurso – grįžtu), apskaičiuojamosios funkcijos matematinė samprata – apibrėžiamos nurodant funkcijos reikšmių nustatymo būdą. Natūraliųjų skaičių aibėje N apibrėžta ir reikšmes toje pačioje aibėje įgaunanti funkcija vadinama paprastąja, jei ji yra viena iš trijų funkcijų o, s arba I, kurių reikšmės yra o(x) = 0, kai x ∈ N, s(x) = x + 1, kai x ∈ N ir I(x1,…,xn) = xm, kai x1,…, xn ∈ N ir 1 ≤ m ≤ n. Funkcija vadinama rekursyviąja, jei ji yra viena iš trijų paprastųjų funkcijų, arba gaunama iš paprastųjų funkcijų atlikus su jomis baigtinį skaičių operacijų naudojant kompoziciją, primityviąją rekursiją ir minimizavimą. Kiekvienai rekursyviajai funkcijai galima nurodyti jos reikšmių apskaičiavimo algoritmą. Alonzo Churchas (Jungtinės Amerikos Valstijos) teigė, kad algoritmiškai apskaičiuojamųjų funkcijų aibė sutampa su rekursyviųjų funkcijų aibe. Rekursyviųjų funkcijų aibė sutampa su A. M. Turingo skaičiavimo mašinomis apskaičiuojamųjų funkcijų aibe.
1751