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

Подстановок слово

Нормальная схема преобразуемое

xx ® y xxxyyyzzz

xy ® x yxyyyzzz

yzy ® x yxyyzzz

zz ®. z yxyzzz

yy ® x yxzzz

yxzz

МУХА

Х ® К МУКА

М ® Р РУКА

КА ® ЛОН РУЛОН

РУ ®. СЛ СЛОН

Примеры алгорифмов, использующие специальные символы, аннулирующие и порождающие подстановки:

Удвоение исходной строки

aх ® хbхa

aу ® уbуa

bхх ® хbх

bху ® уbх

bух ® хbу

bуу ® уbу

b ®

a ®.

® a

Обращение исходной строки

aa ® ba

ba ® b

bх ® хb

bу ® уb

b ® .

aху® уaх

aух ® хaу

® a

Содержательная идея рекурсивных функций состоит в том, что все исходные данные (аргументы) задачи и ее решения (значения функций) можно пересчитать, даже если это далекая от математики задача , вроде решения для себя проблемы идти ли на дискотеку, в библиотеку или лучше на футбол…

Осуществив такого рода нумерацию аргументов и значений можно свести решение задач к нахождению функций ставящих в соответствие числовым аргументам числовые значения.

При этом как аргументы, так и функции находятся в области натуральных чисел - 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.Функция проектирования (выбора аргумента). I_i^{( n)} (x₁, x₂,...,x_i,...,x_n) = x_i.

Или частный случай - тождественная функция: I (x) = x.

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

1.Оператор суперпозиции: Позволяет из функции f (у₁, …, у_m) и функций

h₁(x₁,...,x_n), h₂(x₁,...,x_n), ... ,h_m(x₁,...,x_n) сконструировать функцию

f(h₁(x₁,...,x_n), ... , h_m(x₁,...,x_n)).

Например, с помощью оператора суперпозиции можно получить любую константу

S(S( …(Z(x)) …)) = n, где число вложенных функций следования равно n.

Или сдвига числа на константу n, также равную числу вложенных функций следования.

S(S( …(S(x)) …)) = x + n,

2. Оператор примитивной рекурсии. Этот оператор позволяет получит

n + 1-местную функцию из n-местной и n + 2 - местной функций.

Оператор задается двумя равенствами:

f(x₁,...,x_n, 0) = g(x₁,...,x_n)

f(x₁,...,x_n, y) = h(x₁,...,x_n, y-1, f(x₁,...,x_n, y-1))

Позволяет по n+1-местной функции получить n-местную.

Частный случай - функция одного аргумента:

f(0) = const

f(y) = h(y - 1, f(y - 1))

Функции, которые могут быть построены из примитивных с помощью операторов суперпозиции и примитивной рекурсии называются примитивно-рекурсивными.