3. Як працює рекурсія

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

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

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

• запам'ятовується адреса повернення у викликаючу (зовнішню) процедуру;

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

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

procedure Rec(i: integer); { i – лічильник кроків }

begin

if i >0 then Rec(i -1);

writeln(i);

end;

Результатом вихідного виклику буде друк чотирьох чисел:

0, 1, 2, 3.

В даній процедурі водно, що параметри процедури це межі зміни значень лічильника.

Нижче представлена ​​блок-схема, що показує послідовність виконання операторів для Rec(0,3)

Процедура Rec викликається з параметром a = 3. У ній міститься виклик процедури Rec з параметром a = 2. Попередній виклик ще не завершився, тому створюється ще одна процедура і до закінчення її роботи перша процедура свою роботу не закінчує. Процес виклику закінчується, коли параметр a = 0. У цей момент одночасно виконуються 4 примірники процедури. Кількість одночасно виконуваних процедур називають глибиною рекурсії.

Четверта процедура (Rec (0)) надрукує число 0 і закінчить свою роботу. Після цього керування повертається до процедури, яка її викликала (Rec (1)) і друкується число 1. І так далі поки не завершаться всі процедури.

Ще одна графічна інтерпретація цієї процедури може виглядати наступним чином:

Виконання процедури Rec з параметром 3 складається з виконання процедури Rec з параметром 2 і друку числа 3. У свою чергу виконання процедури Rec з параметром 2 складається з виконання процедури Rec з параметром 1 і друку числа 2. І т. д.

М ожна поміняти місцями рекурсивний виклик і оператор друку, як у наступному прикладі.

procedure Rec2(i: integer);

begin

writeln(i);

if i>0 then Rec2(i-1);

end;

Тоді результатом вихідного виклику буде друк чисел:

3, 2, 1.

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

4. Імітація циклу за допомогою рекурсії

Деякі мови програмування не містять циклічних конструкцій зовсім, надаючи програмістам засоби організовувати повторення за допомогою рекурсії (наприклад, Пролог, де рекурсія - основний прийом програмування).

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

Для прикладу зімітуємо роботу циклу for.

procedure Rec(n: integer); begin if n >0 then Rec(n -1); writeln(n); end;	For i:=n downto 0 do writeln(i); або For i:=1 to n do writeln(n-i+1);
procedure Rec2(n: integer); begin writeln(n); if n>0 then Rec2(n-1); end;	For i:=1 to n do writeln(i);
procedure Rec3(n: integer); begin writeln(n); if n>0 then Rec3(n-1); writeln(n); end;	For i:=n downto 0 do writeln(i); For i:=1 to n do writeln(i);