З поняттям рекурсії ми вже зустрічалися: рекурентні співвідношення досить часто зустрічаються в математичних виразах. у визначенні полягає в тому, що визначається поняття визначається через саме це поняття. Прикладом тут може служити визначення висловлювання (див. лекція 5, визначення 5.1). Рекурсія в обчисленнях виступає у формі рекурентних співвідношень, які показують, як обчислити чергове значення, використовуючи попередні.
Наприклад, рекурентне співвідношення
xi = xi-2 + xi-1, де x1 = 1, x2 = 2
задає правило обчислення так званих чисел Фібоначчі.
Іншим прикладом рекурентних співвідношень можуть служити правила обчислення членів арифметичної прогресії
an +1 = an + d, де d - різниця прогресії,
або геометричній прогресії
an +1 = q an, де q - коефіцієнт прогресії.
Ця ідея рекурсії реалізована і в мові Pascal.
Визначення 16.1. Функція (процедура) мовою Pascal називається рекурсивної, якщо в ході свого виконання вона звертається до самої себе.
Наприклад, ми можемо визначити обчислення функції n!
рекурсивно. Як це зробити, показано на малюнку 16.1
function Factorial (n: integer): integer;
begin if n> 0 then Factorial: = Factorial (n-1) * n
else if n = 0 then Factorial: = 1
else writeln ('значення n менше 0')
end {Factorial}
Рис. 16.1. Функція обчислення n! в рекурсивної формі.
Розглянемо докладно, як буде виконуватися звернення до цієї функції, напрмер, при n = 4.
На малюнку 16.2 показаний процес обчислення для випадку Factorial (4).
24 | |||
Рис. 16.2. Обчислення функції Factorial (n) для n = 4.
Спочатку утворюється так званий рекурсивний фрейм № 1 при n = 4. Для цього фрейму відводиться пам'ять і в ньому фіксуються всі значення змінних тіла функції при n = 4. Відзначимо, що у рекурсивному фреймі фіксуються значення всіх змінних функції, крім глобальних.
Потім відбувається виклик Factorial (n) при n = 3. Утворюється фрейм № 2, де фіксуються значення змінних тіла функції при n = 3. При цьому фрейм № 1 також зберігається в пам'яті. З фрейму № 2 відбувається звернення до Factorial (n) при n = 2. У результаті цього звернення утворюється фрейм № 3, де фіксуються значення змінних тіла функції при n = 2 і т.д. до тих пір, поки при черговому зверненні до функції Factorial умова n> 0 не прийме значення false.
Це відбудеться в фреймі № 5. У цьому фреймі ми отримаємо значення Factorial = 1 і передамо це значення у фрейм № 4. Після цього фрейм № 5 буде знищений, оскільки звернення Factorial (n) при n = 0 буде виконано.
У фреймі № 4 ми обчислимо значення Factorial (n) для n = 1. Після чого ми передамо це значення у фрейм № 3, а фрейм № 4 буде закрито, оскільки звернення до Factorial (n) при n = 1 буде закінчено.
Так ми будемо згортати цей ланцюжок фреймів у послідовності, зворотній тій, в якій ми їх породжували, поки не звернемо фрейм № 1. Після чого обчислення функції буде закінчене.
Рекурсія можлива не тільки у разі функцій, але і процедур. Приклад рекурсії для процедур наведено на малюнку 16.3. Там показано опис рекурсивної процедури для роздруківки (виведення на друк) рядка символів в порядку, зворотному їх введенню.
Procedure BackPrint;
var символ: char;
begin read (символ);
if символ = EOL {EOL - End Of Line - спеціальне значення типу
СHAR, відповідне закінчення введення}
then writeln (); {перед початком виведення треба переконатися, що
друкувати будемо з нового рядка}
else begin BackPrint; write (символ) end
end {Procedure}
Рис 16.3. Приклад рекурсивної процедури.
(Непряма рекурсія.) Ітерація і рекурсія.
Неважко помітити подібність між циклічними конструкціями (повтореннями) і рекурсією. На малюнку 16.4 показана схема циклу виду while do і його рекурсивного аналога.
Цикл | Рекурсія |
while Умова Циклу do Тіло Циклу | Procedure Рекурсивний Цикл; begin if Умова Циклу then begin Тіло Циклу; Рекурсивний Цикл else {закінчення рекурсії} end |
Рис. 16.4. Схема організації циклу виду while do
і його рекурсивного еквівалента.
Зверніть увагу, що в правій частині рис. 16.4 можливо зациклення! Треба бути дуже обережним і щоразу, застосовуючи рекурсивну поцедури або функцію, переконатися в їх коректному завершенні. Розглянемо приклад. На малюнку 16.5 наведено алгоритм Евкліда, з яким ми познайомилися на лекції 1, для обчислення НОД (найбільшого загального дільника) у формі звичайної і рекурсивної функції на мові Pascal.
Function НОД (a, b: integer): integer;
begin repeat if a> b then a: = ab else b: = ba untile a = b; НОД: = a end | begin if a = b then НОД: = a; if a> b then НОД: = НОД (ab, b); else НОД: = НОД (ba, a); end |
Рис. 16.5. Циклічна і рекурсивна функції
для обчислення НОД.
Як видно з наведених прикладів на малюнках 16.1 і 16.5, ітерація, тобто цикл завжди може бути замінений його рекурсивним аналогом за схемою, показаної на малюнку 16.4.
З зворотним твердженням про заміну рекурсії итерацией все складніше. На малюнку 16.6 наведено приклад рекурсивної функції, де за схемою (рис. 16.4) рекурсію итерацией замінити не вдається.
в інших випадках
Рис. 16.6. Рекурсивна функція Акермана.
Способи повторного використання процедур і функцій.
Отже, процес абстракції у формі процедури складається з трьох кроків:
Іменування. Присвоїти рутинному алгоритмом унікальне ім'я, яке потім будемо використовувати як ім'я відповідної процедури.
Визначити перед-і Післяумови для створюваної процедури або функції згідно з контекстом їх використання в основній програмі.
Параметрізіовать процедуру. (Скрізь далі, якщо явно не обумовлено, кажучи про процедури, будемо мати на увазі також і функції). Для цього частина передумови і Післяумови в специфікації оформити у вигляді параметрів відповідного типу, частина з яких буде доставляти вихідні дані, а інша частина - результати роботи процедури.
Узагальнити типи параметрів. Проаналізувати всі місця в програмі, де буде звернення до даної процедури на предмет, які типи даних використовуються в цих місцях, як вони співвідносяться з типами параметрів у процедурі. Назвемо сукупність типів даних в місці виклику процедури контекстом звернення до процедури Визначити типи параметрів так, щоб вони відповідали як можна більшій кількості контекстів звернень до процедури.
Реалізувати вийшла абстракцію рутинного алгоритму або у формі процедури, або функції.
Ми не в праві чекати, що виділені нами вже існуючі функції або процедури, які можуть бути нам корисні для створення нашої нової програми, ми зможемо використовувати в тому вигляді, як вони є. Є чотири основні способи адаптації або повторного використання вже існуючих рутинних алгоритмів і процедур для нових цілей. Це - приєднання, вкладення, настройка і злиття.
Приєднання. Цей спосіб передбачає, що якщо у нас є процедура P1 c передумовою Q1 і постусловіем R1 і процедура P2 c перед-і c Післяумови Q2 і R2 відповідно, (причому R1Þ Q2), то ми можемо побудувати процедуру P c передумовою Q1 і постусловіем R2 послідовно соєденіл Р1 і P2 так, як показано на ріс.16.7.
P {Q1}
{Q1} Р1 {R1} |
{R1 Þ Q2}
{Q2} Р2 {R2} |
{R2}
Рис. 16.7. Приєднання процедур Р1 і P2.
Вкладення. Цей спосіб застосовується, коли нова процедура P утворюється вкладенням відомої процедури P2 всередину іншої відомої процедури P1. Вкладення виникає або коли ми явно вставляємо P2 як тіло циклу або як альтернативу в тілі процедури P1, або коли P2 - це параметр для P1.
Настройка. Суть цього способу полягає в тому, що існуючу процедуру Р1 ми або узагальнюємо, або, навпаки, звужуємо у відповідності зі специфікацією Р.
Наприклад, якщо у нас є процедура вибору максимального числа з масиву з 100 натуральних чисел, то легко її можемо узагальнити на випадок масиву з 1000 цілочисельних компонентів.
Злиття. Цей спосіб побудови нової процедури Р за рахунок злиття, об'єднання двох існуючих процедур Р1 і P2.
Наприклад, нехай процедура Р1 вибирає максимальне, а P2 - мінімальне значення в масиві з 100 цілих чисел. Тоді, об'єднавши оператори процедури Р1 і процедури P2 в належному порядку, ми отримаємо процедуру Р, вибирає max і min з 100 цілих чисел.