Рекурсія

Зазвичай об'єкт називають рекурсивним, якщо він містить свою копію в собі або визначений за допомогою самого себе. Наприклад, формула обчислення факторіала

 1, якщо n=0

n! =

 n!=n× (n-1)!, якщо n>0

і цілого ступеня числа

 1, якщо n=0

xⁿ = 

 x× x^n-1, якщо n>0 .

Рекурсія використовується також при формулюванні ряду правил граматики мов програмування (конструкції ідентифікатора, списків, виразу тощо). Так конструкція <список операторів> в бекусовой нормальній формі має вигляд:

<список операторів> :: = <оператор>  <список операторів>; <оператор>.

Під рекурсією у програмуванні розуміється виклик підпрограми із тіла цієї ж самої підпрограми.

Розрізняють пряму і побічну рекурсію. Якщо підпрограма Р явно викликає сама себе (Р  Р), вона називається прямо рекурсивною. Коли підпрограма Р містить звернення до підпрограми Q, яка в свою чергу містить звернення до Р ( Р  Q  P ), її називають побічно рекурсивною. При непрямому зверненні використання рекурсії в тексті програми не завжди очевидно.

Важливо відзначити, що рекурсія є тільки засобом опису деякого об'єкту, але не задає механізмів реалізації обчислень. Наприклад, при обчисленні n! для n = 4 можна використовувати механізм, зображений на рис 3, який являє собою "спуск" із запам'ятовуванням виразів фунції до тих пір, поки значення виразу не може бути обчислено, а потім "підйом" з обчисленням проміжних значень аж до шуканого.

Рис. 3. Схематичне представлення процесу рекурсії

Кожен раз, коли підпрограма рекурсивно викликається, для неї створюється нова множина локальних змінних. Хоча вони мають ті ж імена, що й елементи множини локальних змінних, створеної при попередньому зверненні до цієї ж підпрограми, їх значення різні. Виключити конфлікт при використанні імен дозволяє правило, яке визначає, що ідентифікатори завжди посилаються на створену останньою множину змінних. Те ж правило відноситься і до параметрів підпрограм.

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

Надійний спосіб забезпечити закінчення процедури аналогічний способу, що застосовується для тих же цілей в операторів циклу. Він полягає у визначенні деякої, наприклад, монотонно спадної функції f(x) (x - множина змінних підпрограми), такої, що її рівність нулю f(x)=0 задовольняє умові закінчення підпрограми. Найчастіше це пов'язаний з підпрограмою параметр (нехай - n), який при рекурсивному виклику підпрограми зменшується на одиницю.

Так, наприклад, обчислення факторіала по його рекурсивному опису зводиться до того, що "граничне значення" визначається явним чином як f (0) = 1, а наступні числа зазвичай визначаються рекурсивно, тобто за допомогою попереднього значення: f (і +1) = f (і) * (і +1).

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

Function Fact (n : word) : longint;

begin

if n>0 then Fact := n* Fact (n-1);

else Fact := 1;

end.

Трасування даної підпрограми:

n = 4

4 >0 (n > 0), Fact = 4 * Fact (3) =

= 4 * 3 * Fact (2) =

= 4 * 3 * 2 * Fact (1) =

= 4 * 3 * 2 * 1 * Fact (0) - кінець обчислень, тому що Fact (0) = 1.

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

Function Step (x:real; n : word) : real;

begin

if n>0 then Step:= x* Step(x, n-1);

else Step:= 1;

end.

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

Незважаючи на наочність рекурсивних описів, у багатьох випадках ті ж задачі більш ефективно вирішуються ітераційними методами, які не вимагають зайвої пам'яті при порівняно однаковій швидкості обчислень. Наприклад, функція обчислення цілого ступеня числа х може бути переписана у такий спосіб:

Function Step (x:real; n : word) : real;

var m:real; i : word;

begin

m:=1;

for i:=1 to n do m:=m*x;

Step:=m;

end.

Рекурсивні процедури і функції використовуаються у тому випадку, коли вихідну задачу можна розділити на підзадачі, що мають ту ж структуру, що і вихідна задача.

Модулі

Подальшим розвитком апарату підпрограм є модулі - абстракція більш високого рівня, яка використовується як основний засіб створення бібліотек.

Модуль - це спеціальним образом оформлена бібліотека описів (констант, змінних, типів, підпрограм), яку можна використовувати усередині будь-якої програми.

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

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

• для використання підпрограм, що входять до складу модуля, достатньо тільки "підключити" модуль до своєї програми (у Pascal - за допомогою спеціальної інструкції uses, у С - за допомогою директиви препроцесора include);

• не потрібно включати вихідний текст підпрограм у програму;

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

• до складу системи програмування включені стандартні модулі, що дозволяють використовувати досить широкий набір визначених підпрограм, які згруповані в ці модулі за певними ознаками (наприклад, в модуль System у мові Pascal включені процедури і функції, що забезпечують введення-виведення, операції з даними певних типів та ін.; модуль Crt підтримує роботу з екраном відеотерміналу і т. д.);

• бібліотека модулів може доповнюватися "власними" модулями користувача.