Рекурсія

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

Прямою (безпосередньої) рекурсією є виклик функції усередині тіла цієї функції.

іnt a()

{.....a()....}

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

Наприклад:

Всі функції a, b, c є рекурсивними, тому що при виклику однієї з них, здійснюється виклик інших і самої собі.

Розглянемо завдання про Ханойські вежі.

2 Ханойські вежі (рекурсивні алгоритми)

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

4 Правила гри

Вимагається перенести пірамідку з одного стержня на інший, використовуючи третій стержень як проміжного і дотримуючи наступні правила:

· за одну дію можна переносити тільки одне кільце;

· кільце можна укладати або на вільний стержень, або на більше кільце.

Вирішимо спочатку найпростіше завдання - для пірамідки з двох кілець.

Позначимо стержні номерами:

1лівий стержень, на якому знаходиться пірамідка на початку гри

2середній стержень, допоміжний

3правий стержень, на нього потрібно перенести пірамідку

Трохи складніше вирішити завдання для пірамідки з трьох кілець. Зверніть увагу, що нижнє кільце можна класти тільки на порожній стержень. А для цього нам потрібно верхні два кільця перекласти на середній стержень, скориставшись алгоритмом Ханой-2. Потім переносимо велике кільце на третій стержень і, знову використовуючи алгоритм Ханой-2, переносимо два менші кільця на третій стержень.

У цьому алгоритмі ми двічі використовували алгоритм Ханой-2, але при цьому різні стержні виступали кінцевим і допоміжним.

Ханой-4 {

/* переносимо три кільця на другий стержень */

Ханой-3 (1,2,3);

/* переносимо нижнє кільце на третій стержень */

1 à 3;

/* переносимо три кільця з другого на третій */

Ханой-3 (2,3,1);

}

Загальний алгоритм для n кілець.

1. Переносимо n - 1 кілець на другий стержень

2. Переносимо нижнє кільце на третій стержень

3.Переносимо n - 1 кілець з другого на третій

Рішення для піраміди з n кілець можна записати у такому вигляді:

Ханой ( n, nach, kon, vspom)

{

якщо n > 1, то

Ханой ( n - 1, 1, 2, 3 );

початковий ( кінцевий;

якщо n > 1, то

Ханой ( n - 1, 2, 3, 1 );

}

Тут в якості початкового, кінцевого і допоміжного можна використовувати будь-які стержні. Алгоритм Ханойфактично пропонує вирішувати задачу дляnкілець через два завдання для меншого числа кілець (n - 1). Такий прийом в програмуванні називається рекурсія.

4 Що таке рекурсія?

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

Тепер ми познайомилися з четвертим видом алгоритмів - рекурсивним алгоритмом. Помітимо, що для перенесення пірамідки з двох кілець потрібно всього 3 ходи, для трьох кілець - вже 3+1+3=7 ходів, для чотирьох - 15 і так далі. Можна показати, що для перенесення пірамідки з n кілець нам буде потрібно ходів. У ченців древнього Ханоя була пірамідка з 64 кілець і вони вірили, що коли вдасться перенести усю пірамідку на третій стержень, настане кінець світу. Отже, це легенда, але число насправді дуже велике і для того, щоб зробити стільки ходів, не вистачить декількох людських життів.

Рекурсію має сенс використовувати тоді, коли в результаті початкове завдання зводиться до більше за просту. Доведено, що будь-який рекурсивний алгоритм можна замінити алгоритмом без рекурсії (який іноді може бути дуже громіздким). Оскільки використання рекурсії в реальних програмах пов'язане з деякими технічними проблемами, краще її не застосовувати, якщо є простий не рекурсивний алгоритм.

Нижче наведена програма, що вводити число n і друкує список переміщень, що вирішує завдання про Ханойські вежі при кількості дисків n. Використовується внутрішня рекурсивна процедура tn(n, і, j, w), що друкує переміщення, необхідні для перенесенню n дисків зі стрижня й на стрижень j з використанням допоміжного стрижня w при {і, j, w} = {1,3,2}.

Послідовність викликів процедури tn при m=3 ілюструється деревоподібною структурою на рис.33. Щораз при виклику процедури tn під параметри n, nach, kon, w виділяється пам'ять і запам'ятовується місце повернення. При поверненні із процедури tn пам'ять, виділене під параметри n, nach, kon, w, звільняється й стає доступної пам'ять, виділена під параметри n, nach, kon, w попереднім викликом, а керування передається в місце повернення.

Рис.33. Послідовність викликів процедури tn

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

Припустимо, що є ситуація:

Тут у функції maіn викликається рекурсивна функція f. Потрібно замінити опис функції f і її виклику на еквівалентний фрагмент програми, тобто видалити функцію f.

Нехай рекурсивна функція f має параметри Р1, Р2,...,Рs, внутрішні змінні V1, V2,...,Vt і у функціях maіn і f є k звертань до функції f. Для видалення такої функції потрібні наступні додаткові об'єкти :

- змінні AR1, AR2,...,ARs, що містять значення фактичних параметрів при виклику функції f (типи змінних повинні відповідати типам параметрів Р1, Р2,...,Рs);

- змінна rz для результату, що обчислюється функцією f (тип змінних збігається з типом значення функції, що повертається, f);

- стік, що містить у собі всі параметри й всі внутрішні змінні функції f, а також змінну lr типу іnt, для зберігання крапки повернення, і змінну pst типу покажчик, для зберігання адреси попереднього елемента стека;

- покажчик dl для зберігання адреси вершин стека;

- проміжний покажчик u для операцій над стеком;

- k нових міток L1,...,Lk для позначених крапок повернення;

- мітка jf, використовувана для обходу модифікованого тіла функції f;

- проміжна змінна l типу іnt для передачі номера крапки повернення.

Щоб одержати еквівалентну не рекурсивну програму без функції f, необхідно виконати наступні дії:

1. Забрати оголошення функції f у функцію maіn;

2. Додати у функції maіn оголошення змінних AR1, AR2,...,ARs, RZ, оголошення стека ST і покажчиків dl і u:

3. Модифікувати тіло функції f у фрагмент програми. Для цього треба:

а) видалити заголовок функції f;

б) оголошення параметрів і внутрішні змінних і замінити фрагментом:

в) наприкінці функції f поставити мітку JF, а всі звертання до формальних аргументів замінити обігом, до відповідних елементів стека;

г) замість кожного оператора return(y) у функції f записати фрагмент:

4. Кожний і виклик функції f (як у зухвалій функції, так і в тілі функції f) виду V=f(A1, A2,...,As) замінити фрагментом програми :

де l=і позначає l=1 при першому звертанні до функції f, l=2 при іншому обігу й т.д. Нумерація обігів може бути виконана в довільному порядку й потрібно для повернення в крапку виклику за допомогою операторів swіtch і goto Lі; (де Lі є L1 при першій заміні, Lі є L2 при другій заміні й т.д.)

5. Вставити модифіковане тіло функції f наприкінці функції maіn.

Для ілюстрації викладеного розглянемо кілька варіантів реалізації програми що обчислює функцію Акермана, що визначається так:

Наступна програма обчислює функцію Акермана з використанням рекурсивної функції ackr і допоміжної функції smacc:

Модифікуючи функції maіn і ackr відповідно до викладеного методу одержимо наступну програму:

Практика

Описати процедуру AddRightDigit(D, K), що додає до цілого позитивного числа K справа цифру D (D — вхідний параметр цілого типу, що лежить в діапазоні 0-9, K — параметр цілого типу, що являється одночасно вхідним і вихідним). За допомогою цієї процедури послідовно додати до цього числа K справа ці цифри D1 і D2, виводячи результат кожного додавання.

Описати процедуру SortArray(A, N), виконуюче сортування за збільшенням речового масиву A розміру N. Масив A є вхідним і вихідним параметром. За допомогою цієї процедури відсортувати масиви A, B, C розміру NA, NB, NC відповідно.

Описати рекурсивну функцію Fact(N) речового типу, що обчислює значення факторіалу

N! = 1*2*...*N

(N > 0 — параметр цілого типу). За допомогою цієї функції вичислити факторіали п'яти цих чисел.

Іспит

На кінець місяця студенти повинні знати:

- перехід від запису алгоритму у вигляді блок-схеми, до запису на мові Сі;

- принцип організації двовимірних і багатовимірних масивів, способи введення-виводу;

- способи сортування масивів і пошуку елементів масиву;

- принципи організації процедур і функцій, передачі ним параметрів і зони видимості змінних;

- принципи роботи рекурсивних підпрограм;

Уміти вирішувати завдання:

- створення і сортування багатовимірних масивів за певним законом;

- видалення елементів з масиву;

- модифікації двовимірних масивів;

- створення покажчиків на змінні і масиви, встановлювати і набувати їх значень;

- складання тексту програми з використанням процедур і функцій;

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

3-й місяць "Файли"

Практика. «Вдосконалення роботи з масивами і функціями»

Описати рекурсивну функцію Fib1(N) цілого типу, обчислюючи N -й елемент послідовності чисел Фібоначчі (N — ціле число) :

F1 = F2 = 1, FK = FK - 2 + FK - 1, K = 3, 4, .

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

Описати процедуру Split1(A, NA, B, NB, C, NC), що формує по речовому масиву A розміру NA два речові масиви B і C розміру NB і NC відповідно; при цьому масив B містить усі елементи масиву A з непарними порядковими номерами (1, 3, .), а масив C — усі елементи масиву A з парними номерами (2, 4, ...). Масиви B і C і числа NB і NC є вихідними параметрами. Застосувати цю процедуру до цього масиву A розміру NA і вивести розмір і вміст отриманих масивів B і C.

Описати рекурсивну функцію MaxElem(A, N) цілого типу, яка знаходить максимальний елемент цілочисельного масиву A розміру N (1 < N < 10), не використовуючи оператор циклу. За допомогою цієї функції знайти максимальні елементи масивів A, B, C розміру NA, NB, NC відповідно.

Дана матриця розміру M х N. Упорядкувати її рядки так, щоб їх перші елементи утворювали зростаючу послідовність.

Лекція 1. "Символьні рядки"

● що таке символьний рядок

● уведення-виведення символьних рядків

● операції над рядками

● рядки у функціях і процедурах

Лекція №14 "Символьних рядків"

План

- вступ (суть лекції)

- що таке символьний рядок

- уведення-виведення символьних рядків

- операції над рядками

- рядки у функціях і процедурах