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

P ≡ P[S, P]

Для виразу рекурсивних програм необхідно і достатньо мати поняття підпрограми, оскільки вони дозволяють дати будь-якому оператору ім'я, за допомогою якого до даного оператора можна звертатися. Якщо деяка процедура Р містить явне посилання на саму себе, то її називають прямо рекурсивною. Якщо ж Р посилається на іншу процедуру Q, що містить (пряме і непряме) посилання на Р, то Р називають побічно рекурсивною. Тому по тексту програми рекурсивність не завжди явно визначна.

Як правило, із процедурою зв'язують сукупність локальних об'єктів, тобто сукупність перемінних, констант, типів і процедур, що визначені тільки в цій процедурі і поза неї не існують або не мають змісту. При кожній рекурсивній активації такої процедури породжується нова сукупність локальних зв'язаних перемінних. Хоча вони мають ті ж самі імена, що і відповідні елементи локальної сукупності попереднього "покоління" цієї процедури, та їхні значення відмінні від останніх, а будь-які конфлікти по іменах розв’язуються за допомогою правил, що визначають область дії ідентифікаторів. За цими правилами ідентифікатор завжди відноситься до самої останньої породженої сукупності перемінних. Це ж правило справедливе і для параметрів процедури, по визначенню зв'язаних із самою процедурою.

Подібно операторам циклу, рекурсивні процедури можуть приводити до обчисленням, що не закінчуються, і тому на цю проблему варто особливо звернути увагу. Очевидно, для того щоб робота коли-небудь, завершилася, необхідно, щоб рекурсивне звертання до Р управлялося б деякою умовою В, що у якийсь – то момент перестає виконуватися. Зокрема, найбільш надійний спосіб забезпечити закінчення процедури у явному вигляді. Для цього ввести в неї будь який параметр (значення), назвемо його п, і при рекурсивному звертанні до Р в якості параметра задавати nзменшене на одиницю, тобто n–1. Якщо в цьому випадку в якості умови В використовується п > 0, то закінчення гарантоване. Це положення може бути виражено двома схемами:

P(n) ≡ if n>0 then P[S,P(n – 1)]

або P(n) ≡ P[S, if n>0 then P(n – 1)].

У практичних додатках важливо переконатися, що максимальна глибина рекурсій не тільки кінцева, але і досить мала.. Справа в тім, що кожна рекурсивна активація процедури Р вимагає пам'яті для розміщення її перемінних. Крім цих локальних перемінних потрібно ще зберігати поточний стан обчислень, щоб можна було повернутися до них по закінченні нової активації. В програмному прикладі 6.1 показано фрагмент рекурсивної підпрограми rec і програми, з якої вікликається вказана підпрограма.

{===== Програмний приклад 6.1 =====}

function rec(i:byte):real;

begin temp:=0;

if i=0 then rec:=i

else temp:=temp+rec(і–1);

/* (адреса ret2) І ця адреса буде записуватися с стек */

rec:=temp;

end;

begin {program}

. . .

n:=rec(3);

/* (адреса ret1); Ця адреса буде записуватися с стек */

a:=n+d;

. . .

end.

Коли рекурсивна функція rec викликається з програми, на стек пишуться: параметр – 3 (при першому виклику) і адреса повернення ret1. При виконанні функції активізуються ще послідовності з 3 викликів (при наступних рекурсивних викликах). І щораз на стек пишеться параметр, що зменшується на одиницю, і адреса повернення ret2. При звертанні до функції з параметром 0 виникає умова останова, і зі стека виштовхується самий верхній запис. Управління передається до оператора за адресою ret2; обчислюється деяка а; виштовхується зі стека наступна пара записів. І так поки стік не стане пустим..