Рекурсія

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

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

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
16.5кб. | скачати

© Усі права захищені
написати до нас