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

 

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, х) = х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.

 

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