Математическая энциклопедия - рекурсия

способ определения функций, являющийся объектом изучения в теории алгоритмов и других разделах математич. логики. Этот способ давно применяется в арифметике для определения числовых последовательностей (прогрессии, чисел Фибоначчи и пр.). Существенную роль играет Р. в вычислительной математике (рекуррентные методы). Наконец, в теории множеств часто используется трансфинитная Р.

Долгое время термин "Р" употреблялся математиками, не будучи точно определенным. Его приблизительный интуитивный смысл можно описать следующим образом. Значение искомой функции f в произвольной точке (под точкой подразумевается набор значений аргументов) определяется, вообще говоря, через значения этой же функции в других точках к-рые в каком-то смысле "предшествуют" . (Само слово "рекурсия" означает "возвращение".) Конечно, в нек-рых "исходных" точках значения f должны задаваться непосредственно. Иногда при помощи Р. определяются одновременно несколько функций; тогда вышеприведенные разъяснения нуждаются в соответствующей модификации. Примеры разнообразных Р. будут даны ниже. Отношение предшествует (где принадлежат области определения искомой функции) в разных видах Р. ("рекурсивных схемах") может иметь разный смысл, однако оно должно быть "фундированным" (т. е. не должно существовать бесконечной последовательности точек такой, что предшествует ). Кроме того, неявно подразумевается, что оно является "достаточно естественным" (напр., желательно, чтобы это отношение усматривалось из самого описания рекурсивной схемы, а не из процесса ее применения). Последнее условие имеет чисто эвристич. значение (напр., для определения каких-нибудь специальных, сравнительно простых видов Р.). Уточнение этого условия по существу неотделимо от уточнения самого понятия Р., а для этого необходимо установить, какого рода формальные выражения могут быть признаны в качестве рекурсивных определений. В тех случаях, когда речь идет о рекурсивных описаниях числовых функций (т. е. функций от натуральных аргументов и с натуральными значениями), обычно подразумевается, что такие описания задают способ вычисления определяемых функций. Ниже всюду (кроме заключительных замечаний) термин "Р." будет пониматься именно в таком смысле. Простейшей и наиболее употребительной рекурсивной схемой является примитивная Р.:

где функции g, h предполагаются известными, f определяемая функция, у - переменная, по к-рой ведется P., x1,. . ., х п - параметры, не участвующие в Р. Ближайшим обобщением этой схемы является т. н. в о з в р а т н а я Р., охватывающая такие виды рекурсивных определений, у к-рых, подобно примитивной P., только одна переменная участвует в Р., а соответствующее отношение предшествования совпадает с обычным упорядочением натуральных чисел (иногда, впрочем, этот термин употребляется и в более широком смысле). Наиболее типичная разновидность в о з в р а тн о й Р. такова:

где . Представляет интерес тот факт, что возвратную Р. можно заменить конечным числом примитивных Р. и подстановок. Другой пример рекурсивной схемы, сводящейся к примитивной Р., даст о д н о в р е м е н н а я Р. вида

где i=l,. . ., k. Математич. логика часто имеет дело с п р и м и т и в н о р е к у р с и в н ы м и функциями, т. е. с такими, к-рые можно получить за конечное число шагов при помощи подстановок и примитивных Р., исходя из нек-рого фиксированного запаса совсем простых функций (напр., и т. п.). Последовательность функциональных равенств, описывающая такое построение, наз. примитивно р е к у р с и в н ы м о п и с а н и е м соответствующей функции. Эти описания суть синтаксич. объекты (т. с. цепочки символов), обладающие определенной эффективно распознаваемой структурой. Практически все числовые функции, употребляемые в математике по какому-либо конкретному поводу, оказываются примитивно рекурсивными. Этим в значительной мере объясняется интерес к данному классу функций.

Более сложные виды рекурсивных определений получаются, когда Р. идет сразу по нескольким переменным. Такие определения, вообще говоря, выводят из класса примитивно рекурсивных функций, хотя соответствующее отношение предшествования может выглядеть как вполне естественное. Напр., в определении f(x, у )могут участвовать значения f(u, v), где u<xили и=х, v<y, как это имеет место в следующей схеме д в ук р а т н о й Р.:

Эта схема уже не сводится к примитивной Р. С другой стороны, к ней сводимы многие более сложные рекурсивные определения (см. [1]).