Урок № 13

(згідно робочої навчальної програми)

Поняття рекурсії. Зовнішні оголошення та оголошення процедур та функцій з випередженням

Питання для вивчення:

1. Поняття рекурсії.

2. Рекурсія зсередини.

Поняття рекурсії. Підпрограми в Паскалі можуть звертатися самі до себе. Таке звернення називається рекурсією. Для того щоб таке звернення не було нескінченним, в тексті підпрограми повинно бути умова, по досягненню якої подальше звернення до підпрограмі не відбувається.

Приклад. Розглянемо математичну головоломку з книги Ж. Арсак «Програмування ігор і головоломок».

Побудуємо послідовність чисел таким чином: візьмемо ціле число i> 1. Наступний член послідовності дорівнює i / 2, якщо i парне, і 3 i +1, якщо i непарне. Якщо i = 1, то послідовність зупиняється. Математично кінцівка послідовності незалежно від початкового i не доведена, але на практиці послідовність зупиняється завжди.

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

Program Arsac;

Var first: word;

Procedure posledov (i: word);

Begin

Writeln (i);

If i = 1 then exit;

If odd (i) then posledov (3 * i +1) else posledov (i div 2);

End;

Begin

Write ('введіть перше значення'); readln (first);

Posledov (first);

Readln;

End.

Програміст розробляє програму, зводячи вихідну задачу до більш простої. Серед цих завдань може виявитися і початкова, але в спрощеній формі. Наприклад, для обчислення F (N) може знадобитися обчислити F (N-1). Іншими словами, частиною алгоритму обчислення функції буде обчислення цієї ж функції. Алгоритм, який є своєю власною частиною, називається рекурсивним. Часто в основі такого алгоритму лежить рекурсивне визначення.

Приклад рекурсивного алгоритму N! = (N-1)! * N, якщо N = 0, то N! = 1

Будь-яке рекурсивне визначення складається з двох частин. Одна частина визначає поняття через нього ж, інша частина - через інші поняття. Приклад рекурсивного алгоритму 2n = 2 n-1 * 2, якщо n = 0, то 2 n = 1.

Процедура є рекурсивною, якщо вона звертається сама до себе прямо або непрямо (через інші процедури).

Все сказане про процедури цілком відноситься і до функцій. Приклад рекурсивної функції обчислення факторіала:

Function factorial (N: integer): longint;

Begin

If N = 0 then

Factorial: = 1

Else Factorial: = factorial (N-1) * N

End;

Рекурсія зсередини. Це може здатися дивним, але самовиклик процедури нічим не відрізняється від виклику іншої процедури. Що відбувається, якщо одна процедура викликає іншу? У загальних рисах наступне:

• в пам'яті розміщуються параметри, передані процедурі (але не параметри-змінні!);

• в іншому місці пам'яті зберігаються значення внутрішніх змінних, які викликаються;

• запам'ятовується адреса повернення в процедуру;

• управління передається спричиненій процедурі.

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

Нехай рекурсивна процедура Power (X, N, Y) зводить число X в ступінь N і повертає результат Y.

Приклад рекурсивної процедури, що зводить число до степеня

Procedure Power (X: real; N: integer; var Y: real);

Begin

If N = 0 then

Y: = 1

Else Begin Power (X, N-1, Y);

Y: = Y * X;

End;

End;

Питання для контролю вивченого матеріалу:

1. Що являє собою рекурсія?

2. Для яких цілей використовують рекурсивні алгоритми?

Література:

Шпак Ю. А. Turbo Pascal 7.0 на примерах/Под ред.Ю. С. Ковтанюка — К.: Издательство Юниор, 2003. — 496 стор., ил., стор 70-73