'''Рекурсивні функції''' — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують [[алгоритм]]и, при найширшому розумінні алгоритмаалгоритму, співпадає з класом рекурсивних функцій. В зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в [[математична логіка|математичній логіці]], основах математики та [[кібернетика|кібернетиці]], як функції ефективно обчислювальніобчислювані функції. Тільки такі функції можна обчислювати на електроних обчислювальних машинах та інших цифрових пристроях.
При введенні класакласу ефективно обчислюваних функцій природнім чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу [[арифметизація математики|арифметизації]], запропонованого [[австрія|австрійським]] математиком [[Гедель|Куртом Геделем К.]], всі такі об'єкти легко зводяться до [[натуральні числа|натуральних чисел]]. Тому рекурсивні функції було введено як функції, що визначені на множині натуральних чисел і набувають значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, [[граф (математика)|графів]], тощо) не маєстворює принципових ускладнень.
<center>'''{{повідомлення|Далі, під словом «функція» слід розуміти функцію, визначену на множині натуральних чисел зі значеннями із множини натуральних чисел.'''</center>}}
