Рекурсія

Рекурсія – це одна з фундаментальних концепцій в математиці та програмуванні.

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

Наприклад, формула обчислення факторіала числа n

ì 1,якщо n=0

n! =í

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

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

ì1,якщо n=0

xⁿ = í

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

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

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

Рекурсія досить поширене явище, яке зустрічається не тільки в галузях науки, але і в повсякденному житті. Наприклад, ефект Дроста, трикутник Серпінського і т. ін.

Трикутник Серпінського	Ефект Дроста

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

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

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

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

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

Зазначений вище процес "спуску", який відбувається доти, доки параметр підпрограми не сягне свого граничного значення, називають рекурсивним зануренням; зворотній процес - "підйом" з підпрограми, що відбуваєтьсядоти, доки параметр не сягне початкового значення- рекурсивне повернення (рис. 4).

Рис. 4. Схематичне представлення процесу рекурсивного занурення та рекурсивного повернення

Величина, що характеризує максимальну кількість незавершених рекурсивних викликів, називається глибиною рекурсії.

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

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

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

Надійний спосіб забезпечити закінчення процедури - аналогічний способу, що застосовується для тих же цілей в операторах циклу. Він полягає у визначенні деякої, наприклад, монотонно спадної функції 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.

Реалізація рекурсивної функції обчислення факторіала числа у мові С/С++:

long int Fact(int n)

{ if (n==0) return 1;

else return Fact(n-1)*n;

}

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

У другому випадку виявляється, що підпрограма, яка описується першою, повинна викликати ще не описану. Щоб це було можливо, потрібно використовувати випереджальний опис (директива forward у Pascal, прототипи функцій – у С/С++).

При непрямому зверненні використання рекурсії в тексті програми не завжди очевидно.

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

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

Наприклад, ввівши позначення для факторіала числа n, отримаємо рекурентне співвідношення

Тоді функція обчислення факторіала числа може бути переписана у такий спосіб:

unsigned long fact(int n)

{unsigned long factorial=1;

for (int i=2;i<=n;i++)

factorial*=i;

return factorial;

}

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

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

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

Отримання цифр двійкового числа, як відомо, відбувається за допомогою ділення із залишком на основу системи числення 2. Якщо є число x, то його остання цифра в його двійковому поданні в C/C++дорівнює залишку від ділення цього числа на 2. Взявши ж цілу частину від ділення цього числа на 2, отримаємо число, що має те ж двійкове представлення, але без останньої цифри. Таким чином, досить повторювати наведені дві операції поки після чергового ділення не отримаємо цілу частину рівну 0. Без рекурсії у С/С++ це буде виглядати так:

while (x>0)

{ c=x%2;

x=x/2;

cout<<c;

}

cout<<endl;

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

int BinaryRepresentation(int n)

{int c;

c=n%2; n=n/2;

if (n>0) BinaryRepresentation(n);

cout<<c;

return c;

}

int main()

{ int x;

cout<<"Enter x: "; cin>>x;

cout<<"BinaryRepresentation "<<x<<" - ";

BinaryRepresentation(x); cout<<endl;

system("pause");

}

Модулі

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

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

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

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

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

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

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

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

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

[1] Сигнатура функції – частина прототипу функції, яка включає її ім’я та типи параметрів