[ЗМІСТ] [Далі] [Назад] [Початок розділу]

6.4. Рекурсивні підпрограми

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

Приклад 6.15. Факторіал f(n) = n!

f(0) = 1;

f(n+1) = f(n)*(n+1).

Приклад 6.16. Добуток натуральних чисел g(n, m) = n*m.

g(0, m) = 0;

g(n+1, m) = g(n, m)+m.

Приклад 6.17. Степінь з натуральним показником h(n, х) = хⁿ.

h(0, х) = 1;

h(n+1, х) = h(n, х)*х.

Визначення з прикладів 6.15-6.17 є варіантами так званої примітивної рекурсії на множині натуральних чисел.

Скажемо, що функція f натурального аргументу n задана схемою примітивної рекурсії, якщо її визначення має вигляд

a) f(0) = c;

b) f(n+1) = j(n, f(n)), (6.6)

де j - деяка задана функція.

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

a) f(0, х, ..., х ) = h (х, ..., х );

1 m 1 m

b) f(n+1, х, ..., х ) = j (n, х, ..., х, f(n, х, ..., х )), (6.7)

1 m 1 m 1 m

де j і h - задані функції.

Функція прикладу 6.15 задана схемою (6.6), причому c = 1, j(n, t) = t*(n+1); для прикладу 6.16 маємо h (х) = 0, j(n, х, t) = t+х; в прикладі 6.17 h (х) = 1, j(n, х, t) = t*х.

Функцію, задану схемою примітивної рекурсії (6.6), можна обчислити підпрограмою-функцією, побудованою за наступною схемою:

функція f (n: нат): t це

змін у: t;

поч

якщо n=0 то у <- c

інакше у <- j(n-1, f(n-1)) кр;

f <- у

кф.

Відмітимо, що визначення функції f виявилося рекурсивним – в тілі функції міститься виклик її самої.

Застосувавши цей метод до примітивно-рекурсивного визначення факторіала, отримаємо

Приклад 6.15'. Рекурсивна функція для обчислення факторіала.

функція Fact (n: нат): нат це

змін у: нат;

поч { Fact(n) = n! }

якщо n=0 то у <- 1

інакше у <- n*Fact(n-1) кр;

Fact <- у

кф.

Подивимося, як застосовується правило виклику функції з п.6.1 в цьому випадку, обчисливши, наприклад, Z= Fact(3).

--------------------------------------------------------------

Z k n1 y1 n2 y2 n3 y3 n4 y4 F1 F2 F3 F4

--------------------------------------------------------------

....................... 3

Z <- Fact(k)

---------------------

¦ n1<- k 3

¦ n1=0(ні)

¦ y1<- n1*Fact(n1-1)?

--------------------

¦ n2<- n1-1 2

¦ n2=0(ні)

¦ y2<- n2*Fact(n2-1)?

-------------------

¦ n3<- n2-1 1

¦ n3=0(ні)

¦ y3<- n3*Fact(n3-1)?

------------------

¦ n4<- n3-1 0

¦ n4=0(так)

¦ y4<- 1 1

¦ Fact4<- y4 1

------------------

y3<- 1*Fact(0) 1

Fact3<- y3 1

-------------------

y2<- 2*Fact(1) 2

Fact2<- y2 2

--------------------

y1<- 3*Fact(2) 6

Fact1<- y1 6

--------------------- 6

З іншого боку раніше ми обчислювали факторіал без використання рекурсії.

Приклад 6.15''. Обчислення факторіала без використання рекурсії.

функція Fact1 (n: нат): нат це

змін у, х: нат;

поч { Fact1(n) = n! }

х <- 0; у <- 1;

повт n раз

х <- х+1; у <- у*х

кц;

Fact1 <- у

кф.

Вивчимо один метод порівняння рекурсивних і циклічних (ітеративних) алгоритмів.

Скажемо, що функція F(n, х, у) задана рекурсивним визначенням в ітеративній формі, якщо

a) F(0, х, у) = у;

b) F(n+1, х, у) = F(n, g(х), h(х, у)). (6.8)

Теорема 6.1. Функцію (6.8) можна обчислити за допомогою алгоритму

{ х=a & у=b }

повт n раз

у <- h(х, у);

х <- g(х)

кц

{ у = F(n, a, b) }.

Доведення. Індукція по n.

a) При n=0 отримаємо у = b = F(0, a, b) в силу (6.8 a).

b) Нехай для деякого n при будь-яких а і b, які ми для зручності подальших міркувань перевизначимо через a' і b', твердження теореми має місце:

{ х=a' & у=b' }

повт n раз

у <- h(х, у);

х <- g(х)

кц

{ у = F(n, a', b') }.

c) Розглянемо n+1. Виконання будь-якого циклу n+1 разів можна представити як ланцюжок з одноразового виконання тіла циклу і n-разового повторення. Отримаємо

{ х=a & у=b }

у <- h(х, у); (6.9)

х <- g(х)

{ х=g(a) & у=h(a, b) }.

За припущенням індукції при a' = g(a) і b' = h(a, b)

{ х=g(a) & у=h(a, b) }

повт n раз

у <- h(х, у); (6.10)

х <- g(х)

кц

{ у = F(n, g(a), h(a, b)) }.

Згідно з (6.8 b) F(n, g(a), h(a, b)) = F(n+1, a, b). Об'єднавши (6.9) і (6.10), отримаємо

{ х=a & у=b }

повт n+1 раз

у <- h(х, у);

х <- g(х)

кц

{ у = F(n+1, a, b) },

що і потрібно було довести.¦

Приклад 6.18. Наприклад, якщо функцію F(n, х, у) визначити таким чином

F(0, х, у) = у; F(n+1, х, у) = F(n, х+1, (х+1)*у),

то внаслідок теореми 6.1 можна стверджувати, що алгоритмічною реалізацією функції F(n, 0,1) є програмована функція Fact1(n).

Встановимо зв'язок між примітивно-рекурсивними та ітеративними функціями.

Теорема 6.2. Нехай функція f задана визначенням (6.6), тоді

f(n) = F(n, 0, c),

де функція F задана співвідношеннями

a) F(0, х, у) = у;

b) F(n+1, х, у) = F(n, х+1, j(х, у)). (6.11)

Для доведення використаємо

Лема 6.1. В умовах теореми 6.2 f(n+m) = F (n, m, f(m)).

Доведення проведемо індукцією по n.

a) Нехай n=0. Тоді згідно з (6.11 a)

F(0, m, f(m)) = f(m) = f(0+m).

b) Припустимо, що при деякому n маємо

f(n+m') = F(n, m', f(m')).

c) Розглянемо n+1. Тоді згідно з (6.11 b)

F(n+1, m, f(m)) = F(n, m+1, j(m, f(m))).

В силу (6.6 b)

F(n, m+1, j(m, f(m))) = F(n, m+1, f(m+1)).

Застосувавши припущення індукції при m'=m+1 отримаємо

F(n, m+1, f(m+1)) = f(n+m+1) = f(n+1+m),

що і потрібно було довести.¦

Доведення теореми 6.2 негайно слідує з леми 6.1 при m=0.¦

Аналог теореми 6.2 можна сформулювати також для примітивно-рекурсивного визначення (6.7).

Повертаючись до прикладу 6.15, помітимо, що функція F(n, 0,1) з прикладу 6.18 рівна n! і, отже, відповідь на питання про рівносильність двох функцій дає теорема 6.2.

Теореми 6.1 і 6.2 дають наступний спосіб програмування примітивно-рекурсивних функцій. На першому кроці на основі теореми 6.2 примітивно-рекурсивна функція перетворюється в рекурсивну функцію в ітеративній формі, за якою в силу теореми 6.1 отримуємо шуканий цикл.

Нарешті розглянемо дві задачі, які не підпадають під схему примітивної рекурсії.

Приклад 6.19. Функція Аккермана, задана співвідношеннями

Akk(0, m) = m+1;

Akk(n+1,0) = Akk(n, 1);

Akk(n+1, m+1) = Akk(n, Akk(n+1, m)),

не є примітивно-рекурсивною. Її можна обчислити за допомогою наступної функції

функція Akk (n, m: нат): нат це

змін у: нат;

поч

якщо n=0 то

у <- m+1

інакше

якщо m=0 то

у <- Akk(n-1,1)

інакше

у <- Akk(n, m-1); у <- Akk(n-1, у)

кр

кр;

Akk <- у

кф.

Наступний приклад показує застосування рекурсивних процедур.

Приклад 6.20. Ханойські вежі. Дошка має три стержні. На першому нанизані n дисків спадного вгору діаметра. Потрібно, перекладаючи диски по одному, розташувати їх в колишньому порядку на другому стержні, використовуючи третій стержень для тимчасового зберігання дисків. При цьому більший диск ніколи не повинен розташовуватися над меншим.

Припустимо, що ми вміємо перенести n-1 диск. Тоді правило переміщення n дисків зі стержня А на стержень В з використанням стержня C для тимчасового зберігання дисків можна записати наступним чином:

1) перенести n-1 диск з А на C;

2) перенести 1 диск з А на В;

3) перенести n-1 диск з C на В.

Очевидно, алгоритм має значення при n>1. Отримуємо рекурсивну процедуру

процедура Hanoi (арг n, А, В, C: нат) це

поч

якщо n>0 то

Hanoi (n-1, А, C, В);

показати(А,' -> ', В);

Hanoi (n-1, C, В, А)

кр

кп,

яку можна викликати так: Hanoi (n,1,2,3). При n=3 отримаємо тоді наступну схему вкладених викликів процедури Hanoi(...), яку для скорочення запису визначимо однією буквою Н(...):

------------- Н(3,1,2,3) --------------

¦ ¦ ¦

--- Н(2,1,3,2) ---- 1->2 --- Н(2,3,2,1) ----

¦ ¦ ¦ [4] ¦ ¦ ¦

Н(1,1,2,3) 1->3 Н(1,2,3,1) Н(1,3,1,2) 3->2 Н(1,1,2,3)

¦ [2] ¦ ¦ [6] ¦

Н(0,1,3,2) Н(0,2,1,3) Н(0,3,2,1) Н(0,1,3,2)

1->2 [1] 2->3 [3] 3->1 [5] 1->2 [7]

Н(0,3,2,1) Н(0,1,3,2) Н(0,2,1,3) Н(0,3,2,1)

У квадратних дужках вказана послідовність виконання команди показати(А,' -> ', В), а поряд самі повідомлення на пристрої виведення. Збираючи їх разом отримуємо наступний ланцюг перенесень дисків зі стержня 1 на стержень 2:

1 -> 2 ¦ 1 -> 3 ¦ 2 -> 3 ¦ 1 -> 2 ¦ 3 -> 1 ¦ 3 -> 2 ¦ 1 -> 2.

Зверніть увагу, в цьому випадку виконується 15 викликів процедури Hanoi(...) і при цьому задіяно 15*4=60 додаткових змінних.

6.5. Програмування рекурсивних підпрограм

У мові Паскаль рекурсивні підпрограми допустимі та синтаксично не відрізняються від нерекурсивних.

Приклад 6.4 Р. Ханойські вежі (задача 6.20).

program Han;

var n: byte;

procedure Hanoi (n, A, B, C: byte);

begin

if n>0 then begin

Hanoi (n-1, A, C, B);

writeln(A:1,' -> ', B:1);

Hanoi (n-1, C, B, A)

end

end;

begin

write('К-ть дисків=? '); readln(n);

Hanoi (n,1,2,3)

end.

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

При використанні рекурсивних підпрограм дійсні всі правила мови Паскаль на застосування в програмах процедур та функцій.

У мові Сі рекурсивні підпрограми також допустимі та також не відрізняються від нерекурсивних синтаксично.

Приклад 6.4 С. Ханойські вежі (задача 6.20).

#include <stdio.h>

/* Han */

hanoi(unsigned n, unsigned a, unsigned b, unsigned c)

{

if (n>0)

{

hanoi(n-1, a, c, b);

printf(“%u -> %u\n”, a, b);

hanoi(n-1, c, b, a);

}

}

main()

{

unsigned n;

printf(“К-ть дисків=? ”); scanf(“%u”, &n);

hanoi(n,1,2,3);

}

Задачі та вправи

Вправа 6.4. Сформулювати і довести аналог теореми 6.1 для випадків:

a) F(0, х, у, z) = z;

F(n+1, х, у, z) = F(n, g(х), h(х, у), t(х, у, z));

b) F(0, х, у) = у;

F(n+1, х, у) = F(n, g(х, у), h(х, у)).

Вправа 6.5. Нехай функція F задана співвідношеннями (6.11), довести, що F(n+1, х, у) = j(n+х, F(n, х, у)).

Вправа 6.6. Довести теорему 6.2, використовуючи результат вправи 6.5.

[ЗМІСТ] [Далі] [Назад] [Початок розділу]