Рекурсивні функції

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Рекурсивні функції — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують алгоритми, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій. У зв'язку з цим, рекурсивні функції грають важливу роль в математиці та її застосуваннях, в першу чергу, в математичній логіці, основах математики та кібернетиці, як ефективно обчислювані функції. Тільки такі функції можна обчислювати на електроних обчислювальних машинах та інших цифрових пристроях.

При введенні класу ефективно обчислюваних функцій природнім чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу арифметизації, запропонованого австрійським математиком Куртом Геделем, всі такі об'єкти легко зводяться до натуральних чисел. Тому рекурсивні функції було введено як функції, що визначені на множині натуральних чисел і набувають значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, графів тощо) не створює принципових ускладнень.

Поняття рекурсивних функцій[ред.ред. код]

Базовими примітивними функціями, за визначенням, є:

  1. нульова функція \ O^n(x_1, \dots, x_n) = 0
  2. функція слідування \ s(x)=x+1
  3. функція проектування \ I^n_m(x_1, \dots, x_n) = x_m

Операція суперпозиції[ред.ред. код]

Кажуть, що функція g(x_1, \dots, x_m) виникає із функцій f(x_1, \dots, x_n), f_1(x_1, \dots, x_m), …, f_n(x_1, \dots, x_m) суперпозицією, якщо

\ g(x_1, \dots, x_m) = f \Big( f_1(x_1, \dots, x_m), \dots, f_n(x_1, \dots, x_m)\Big)

Операція примітивної рекурсії[ред.ред. код]

Функція \ f(x_1, \dots, x_{n+1}) утворюється із функцій \ g(x_1, \dots, x_n), \; h(x_1, \dots, x_{n+2}) за допомогою примітивної рекурсії, якщо для всіх натуральних значень \ x_1, \dots, x_n, y маємо

\ f(x_1, \dots, x_n, 0) = g(x_1, \dots, x_n);
\ f(x_1, \dots, x_n, y+1) = h\Big(x_1, \dots, x_n, y, f(x_1, \dots, x_n, y)\Big).

Операція мінімізації[ред.ред. код]

Позначимо через \mu y(f(x_1, \dots, x_{n-1}, y) = x_n) найменше значення \alpha, для якого f(x_1, \dots, x_{n-1}, \alpha) = x_n. Будемо вважати, що \mu y(f(x_1, \dots, x_{n-1}, y) = x_n) не визначено, якщо:

  1. значення f(x_1, \dots, x_{n-1}, \alpha) визначено для всіх y < \alpha, але відмінні від x_n, а значення f(x_1, \dots, x_{n-1}, \alpha) не визначено (α = 0, 1, 2, …) або
  2. значення f(x_1, \dots, x_{n-1}, \alpha) визначені для всіх α = 0, 1, 2, … та відмінні від x_n.

Таким чином, значення \mu y(f(x_1, \dots, x_{n-1}, y) = x_n) є функцією g(x_1, \dots, x_n) від змінних x_1, \dots, x_n. Кажуть, що ця функція отримана від функції f(x_1, \dots, x_{n-1}, y) із допомогою мінімізації.

Примітивно рекурсивна функція[ред.ред. код]

Функція називається примітивно рекурсивною, якщо її можна отримати із функцій \ s(x), \ O^n(x_1, \dots, x_n) та \ I^n_m(x_1, \dots, x_n) скінченною кількістю операцій суперпозиції та примітивної рекурсії.

Частково рекурсивна функція[ред.ред. код]

Функція називається частково рекурсивною, якщо отримана із вказаних функцій застосуванням скінченної кількості операцій суперпозиції, примітивної рекурсії та мінімізації. Всюди визначена частково рекурсивна функція називається загальнорекурсивною.

Одним з популярних прикладів загальнорекурсивної, але не примітивно рекурсивноїї функції є функція Акермана.

Дослідження рекурсивних функцій[ред.ред. код]

Рекурсивні функції, виступаючи як еквівалент поняття ефективно рекурсивних функцій з моменту їх введення піддавались інтенсивному дослідженню.

Перш за все, в класі рекурсивних функцій були виділені та вивчені підкласи простіших функцій — примітивно рекурсивних, елементарних за Л. Кальмару. Доведено, що клас загальнорекурсивних функцій ширший класу примітивно рекурсивний: існують загальнорекурсивні функції, що не є примітивно рекурсивними. Очевидно, що клас частково ширший класу загальнорекурсивних функцій.

Доведено, також, що будь-яка частково рекурсивна функція може бути представлена у вигляді:

g(x_1, \dots, x_s) = \phi (\mu z(f(x_1, \dots, x_s, z) = 0)),

Де \phi і f — примітивно рекурсивні функції, тобто, для отримання будь-якої частково рекурсивної функції оператор μ можна застосувати не більше одного разу.

Робились спроби класифікації рекурсивних функцій. Класифікацію примітивно рекурсивних функцій здійснив польський математик А. Гжегорчик, а класифікацію, основану на понятті звідностітеорії алгоритмів), виконав американський математик Е. Пост.

Алгебри рекурсивних функцій[ред.ред. код]

Також досліджувались алгебри рекурсивних функцій: на множині рекурсивних функцій визначались ті чи інші операції, відносно яких множини функцій утворювали універсальні алгебри. В якості таких операцій обирались операції суперпозиції (*), додавання (+) а також операція обернення f^{-1} визначена схемою f^{-1}(x)=\mu y(f(y)=x), та операція ітерації i, що визначається схемою g(0)=0, g(x+1) = f(g(x)). Нехай s(x) = x+1,


g(x) = \begin{cases}
x, & [\sqrt{x}]^2 \mathrm{yakwo} x > [\sqrt{x}]^2; \\
0, & \mathrm{inakwe}
\end{cases}

де α означає максимальне ціле число, не більше за α.

Доведено, що всі одномісні примітивно рекурсивні функції, і лише вони можуть бути отримані із функцій s(x), g(x) скінченною кількістю операцій додавання, суперпозиції та ітерації.

Аналогічно, кожну загальнорекурсивну функцію можна отримати із функцій s(x), g(x) скінченною кількістю операцій додавання суперпозиції та обернення, при чому останню виконують лише тоді, коли її результатом є всюди визначена функція. Якщо зняти це обмеження, тоді можна отримати всі одномісні частково рекурсивні функції.

Головним чином, досліджувались три алгебри:

  • \mathfrak{A}_{pr}=\langle F_{pr}, +, *, i\rangle
  • \mathfrak{A}_{cr}=\langle F_{cr}, +, *, {}^{-1}\rangle
  • \mathfrak{A}_{gr}=\langle F_{gr}, +, *, {}^{-1} \rangle

де F_{pr}, F_{cr} та F_{gr} — множини всіх одномісних примітивно рекурсивних, частково рекурсивних та загальнорекурсивних функцій. Досліджувались найприродніші питання: наявність скінченних базисів, приклади підалгебр, описання максимальних підалгебр, тобто, таких підалгебр, які не містяться в жодних інших підалгебрах самих алгебр, ізоморфізми та автоморфізми підалгебр, конгруенції на підалгебрах, питання скінченної визначеності алгебри тощо.

Разом із дослідженням рекурсивних функцій, широко досліджуються рекурсивні предикати і пов'язані з ними множини — підмножини множини натуральних чисел.

Рекурсивні функції в програмуванні[ред.ред. код]

Базисний приклад в мові PHP: При створенні нової функції f() в її тілі викликається та сама функція f() зі зміненим аргументом:

function f($x){
 
	# Обчислення та друк добутка числа на 2.
	return $x*2 . '<br />';
	$y=$x*2;
 
	# Виклик функції f() в власному тілі ще раз, але з новим аргументом.
	f($y);
}
 
# Приклад 1: Отримуємо числа добуток 1*2 яких ще раз перемножувався на 2:
# 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 і тд...
print f(1);
 
# Приклад 2: Отримуємо числа добуток 3*2 яких ще раз перемножувався на 3:
# 6, 12, 24, 48, 96, 192, 384, 768, 1536, 3072, 6144 і тд...
print f(3);

Джерела інформації[ред.ред. код]

Див. також[ред.ред. код]