Рекурсія

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

 1, якщо n=0

n! =

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

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

 1, якщо n=0

xⁿ = 

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

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

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

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

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

Рис. 4. Рекурсивні зображення

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

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

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

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

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

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

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

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

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

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

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

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

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

unsigned long fact(int n)

{ if (n==0) return 1;

else return fact(n-1)*n;

}

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

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.

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

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

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

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

Наприклад, ввівши позначення x_n = n! для факторіала числа n, отримаємо рекурентне співвідношення x_n = x_n-1 n, x₀ = 1. Тоді функція обчислення факторіала числа може бути переписана у такий спосіб:

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");

}

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

28