Рекурсія.
З поняттям рекурсії ми вже зустрічалися: рекурентні співвідношення досить
часто зустрічаються в математичних виразах. Рекурсія у визначенні полягає в
те, що визначається поняття визначається через саме це поняття. Прикладом
тут може служити визначення висловлювання (див. лекція 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: = a-b
else b: = b-a
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
