Поняття рекурсії. Зовнішні оголошення та оголошення процедур та функцій з випередженням
Питання для вивчення: 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 Будь-яке рекурсивне визначення складається з двох частин. Одна частина визначає поняття через нього ж, інша частина - через інші поняття. Процедура є рекурсивною, якщо вона звертається сама до себе прямо або непрямо (через інші процедури). Все сказане про процедури цілком відноситься і до функцій. 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
(згідно робочої навчальної програми) ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|