Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Содержательная идея рекурсивных функций состоит в том, что все исходные данные (аргументы) задачи и ее решения (значения функций) можно пересчитать, даже если это далекая от математики задача, вроде решения для себя проблемы идти ли на дискотеку, в библиотеку или лучше на футбол…
Осуществив такого рода нумерацию аргументов и значений можно свести решение задач к нахождению функций ставящих в соответствие числовым аргументам числовые значения.
При этом как аргументы, так и функции находятся в области натуральных чисел - 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-местную.
Частный случай - функция одного аргумента:
f(0) = const
f(y) = h(y - 1, f(y - 1))
Функции, которые могут быть построены из примитивных с помощью операторов суперпозиции и примитивной рекурсии называются примитивно-рекурсивными.
Пример: функция суммирования.
fS(x, 0) = g(x) = I(x) = x
fS(x, 1) = h(x, 0, fS(x, 0)) = h(x, 0, x) = h ` (I3(3)((x, 0, x)) = S(x) = x + 1
fS(x, 2) = h(x, 1, fS(x,1)) = h(x, 1, x+1) = S(x + 1) = x + 2
...
fS(x, y) = h(x, 1, fS(x, y - 1)) = S(fS (x, y - 1)) = x + y
то есть в традиционной записи определение сложения, как примитивно-рекурсивной функции, будет:
x + y = x + (y - 1) + 1
Функция умножения.
fp(x, 0) = y(x) = z(0) = 0
fp(x, 1) = h(x, 0, fp(x, 0)) = h(x, 0, 0) = h ` (I1,3(3)((x, 0, 0)) = fS(x, 0) = x
fp(x,2) = h ` (x, fp(x, 1)) = fS(x, x) = 2x
fp(x,y) = fS(x, fp(x, y - 1))
то есть в традиционной записи определение умножения, как примитивно-рекурсивной функции, будет
x*y = x*(y - 1) + x
Дата публикования: 2014-11-03; Прочитано: 424 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!