Рекурсивні функції
З Вікіпедії, безкоштовно encyclopedia
Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електронних обчислювальних машинах та інших цифрових пристроях.
При введенні класу ефективно обчислюваних функцій природним чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу арифметизації, запропонованого австрійським математиком Куртом Геделем, всі такі об'єкти легко зводяться до натуральних чисел. Тому рекурсивні функції було введено як функції, що визначені на множині натуральних чисел і набувають значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, графів тощо) не створює принципових ускладнень.
![]() | Далі, під словом «функція» слід розуміти функцію, визначену на множині натуральних чисел зі значеннями із множини натуральних чисел. |
![]() | В теорії алгоритмів під словом рекурсивна функція мають на увазі тотальну частково рекурсивну функцію, тобто вужче поняття ніж в цій статті. Якщо вас вчили поняттю ЧРФ - вважайте що далі під терміном "рекурсивна функція" мають на увазі частково рекурсивну. Хоча це все треба уточнити з посиланням на АД |