Специальная математика. Соловьев А.Е. - 69 стр.


Обращение исходной строки
  
  
х  х
у  у
  .
ху ух
ух  ху


                            6.6. Рекурсивные функции

Содержательная идея рекурсивных функций состоит в том, что все исходные данные
(аргументы) задачи и ее решения (значения функций) можно пересчитать, даже если это
далекая от математики задача , вроде решения для себя проблемы идти ли на дискотеку, в
библиотеку или лучше на футбол…
Осуществив такого рода нумерацию аргументов и значений можно свести решение задач к
нахождению функций ставящих в соответствие числовым аргументам числовые значения.
При этом как аргументы, так и функции находятся в области натуральных чисел - N.
Рекурсивные функции строятся на основе трех примитивных (заведомо однозначно
понимаемых и реализуемых) функций.
1. Нуль-функция: Z(x) = 0.
Например, Z(1) = 0, Z(5) = 0., но Z(-5) - не определено.
4. Функция следования: S(x) = x + 1.
Тонкость заключается в том, что операции сложения (+) мы здесь пока не определили и
запись " + 1" понимается как взятие следующего элемента естественно упорядоченного
множества N.
То есть в множестве N. всегда можно найти следующий аргумент, например: S(5) = 6.
3.Функция проектирования (выбора аргумента). Ii( n) (x1, x2,...,xi,...,xn) = xi.
Или частный случай - тождественная функция: I (x) = x.

С примитивными функциями можно производить различные манипуляции, используя три
оператора: суперпозиции, примитивной рекурсии и наименьшего корня.

1.Оператор суперпозиции: Позволяет из функции f (у1, …, уm) и функций
h1(x1,...,xn), h2(x1,...,xn), ... ,hm(x1,...,xn) сконструировать функцию
   f(h1(x1,...,xn), ... , hm(x1,...,xn)).
Например, с помощью оператора суперпозиции можно получить любую константу
S(S( …(Z(x)) …)) = n, где число вложенных функций следования равно n.
Или сдвига числа на константу n, также равную числу вложенных функций следования.
S(S( …(S(x)) …)) = x + n,

2. Оператор примитивной рекурсии. Этот оператор позволяет получит
n + 1-местную функцию из n-местной и n + 2 - местной функций.
Оператор задается двумя равенствами:
     f(x1,...,xn, 0) = g(x1,...,xn)
     f(x1,...,xn, y) = h(x1,...,xn, y-1, f(x1,...,xn, y-1))
Позволяет по n+1-местной функции получить n-местную.
Частный случай - функция одного аргумента:

                                       — 69 —