рекурсивни функции
Ние считаме, че само числови функции, т.е.. Д. аргументите на функции, и чиито ценности принадлежат на снимачната площадка на естествените числа N (N = 0,1,2, ...).
Ако домейнът на функцията съвпада с набора, функцията се нарича навсякъде е определено, или - частично дефинирани.
е (х, у) = х + у - функция дефинирано навсякъде,
е (х, у) = X-Y - частично дефинирана функция, т.е., на определено само за ...
Рекурсивни функции дефиниция - е определение, при което стойността на аргумента функция за данните, определени от стойностите на същата функция за прости стойности на аргументи или повече прости функции.
1. Фибоначи номера (1, 1, 2, 3, 5, 8, ...) е последователност от числа е (п), където е (0) = 1, е (1) = 1, е (п + 2) = F (п) + е (п + 1).
2. факторен (п! = 1 * 2 * 3 * ... * п) е (0) = 1, е (п + 1) = е (п) * (п + 1).
Рекурсивни функции се базира на три примитивен (очевидно ясно разбрани и приложени) функции. Те се наричат също протозои.
1. S (х) = х + 1 - функционални повторение.
Примери. S (0) = 1, S (1) = 2, S (-5) - не е определена.
2. G (х) = 0 - нула-ценен функция;
Примери: G (0) = 0, D (1) = 0 и G (-5) - не е определена.
3. Im (х1, х2, ..., хп) = х, (т = 1,2, ... п) - дизайн функция (аргумент избор).
На примитивните функции могат да изпълняват различни манипулации, с помощта на три оператора: наслагване, примитивна рекурсия и минимизиране.
1. суперпозиция оператор (заместване).
Нека е - т-място функция, g1, ... GM - п-местен операции на набор N. наслагване оператор S възлага на операциите е и G1, ... г п-местен функция часа.
1) Използване на оператора на суперпозиция, можете да получите всяка константа.
S (S ... (О (х)) ...) = 0 + п, където п брой прикачени следните функции.
2) Използване на оператора на състав може да изпълнява изместване при постоянна п.
2. Операторът на примитивна рекурсия
Всеки оператор R (п + 2) операциите -place F и п-местните оперативни възлага на г (п + 1) операция ка з = R (F, G), отговаря на следната схема:
За п = 0 примитивна схема рекурсия има формата:
, където - константа
Пример: Изчислява факториела използване примитивен оператор рекурсия ще бъде както следва.
Схема примитивни форми процес рекурсия за конструиране функция часа, при което в нула стъпка използва функция д, и всяка следваща стъпка от стойността на функцията F аргументи номера у предишната стъпка и стойността на функцията Н, изчислени в предишната стъпка.
Функцията се нарича примитивна рекурсивно (PRF), ако може да бъде получена от първоначалните функции чрез наслагването на оператора или на оператора на примитивна рекурсия.
1) - примитивен рекурсивна функция.
Схемата на примитивна рекурсия:
2) - примитивен рекурсивна функция.
3. За да се сведе до минимум оператор (операторът на)
, където Y - избран променливи.
Работа-оператор може да се опише по следния начин. Разпределени променлива Y, след което се фиксира другите променливи. Стойността на у увеличава последователно, като се започне с 0. стойност операторът ще имат стойност при които функцията се прилага първо до 0.
Ако тази функция не е включена към 0 или отрицателна стойност, стойността е неопределена-оператор.
Ние се определи х = 1 и у ще се промени.
F функцията (х1, х2, ..., хп) е частично рекурсивно (CHRF), ако може да бъде получена от първоначалните функции с помощта на определен брой използва наслагване, примитивен рекурсия и минимизиране.
е (х, у) = X-Y - .. частично, т.е. тя не трябва да се определи, ако х Имоти съкратени разлика. Рекурсивно функция е примитивен, т.е. схемата на примитивна рекурсия ..: По този начин. може да бъде получен от първоначалния функции о (х) и Im (х1, ... хп) с обикновено рекурсия оператор R. По схемата на примитивна рекурсия По този начин. функция може да бъде получена чрез работа на примитивни функциите на рекурсия и Н (х, Y, Z) =. Следователно функция е (х, у) = X-Y е частично рекурсивна функция. Навсякъде определено частично рекурсивна функция е рекурсивен (RUF). За алгоритмични проблеми на типичен случай, когато искате да се намери алгоритъм за изчисляване на числова функция F (x1, ... Xn). Числовите функции, чиито стойности може да бъде изчислена като се използва алгоритъм, наречен изчислимите функции. Тази концепция е интуитивен, т. За. Интуитивният понятието алгоритъм. F функцията (x1, ... хп) е ефективно изчислимо, ако има алгоритъм, който може да се използва за намиране е (k1 ... Кп), ако са известни К1 ... Кп. дисертация Чърч. Всяко ефективно изчислимо функция е частичен рекурсивна функция. дисертация формулиране на Църквата включва понятието за ефективна изчислимост. Поради това не може нито да се докаже, нито отхвърлена в математическия смисъл на думата. Частичен рекурсивни - прецизиране на понятието изчислима функция. Тя може да се използва, за да се усъвършенства или опровергае изчислимост. Всеки частичен рекурсивна функция е изчислимо от Тюринг и обратно.
Свързани статии