Рекурсивними називають функції, які в процесі виконання звертаються самі до себе. Рекурсія може бути безпосередньою (пряма рекурсія) – коли з тіла функції викликається та сама функція, або посередньою (непряма рекурсія) – коли функція викликає інші функції, які безпосередньо або через треті функції звертаються до даної функції.
Здебільшого рекурсивні функції є лаконічними в записі і дають змогу наочно та стисло відобразити алгоритм розв’язання задачі. З іншого боку, рекурсивні звертання часто не легкі для сприйняття, аналізу та контролю. Вони можуть вимагати значних обсягів оперативної пам'яті і призводити до часових затримок в процесі виконання програми.
За способом реалізації рекурсивні виклики рекурсивні виклики функцій нічим не відрізняються від звичайних викликів: кожен раз створюється новий набір формальних параметрів і внутрішніх змінних програми, код функції виконується від самого початку. Результат виконання функції повертається в точку її виклику.
Розглянемо програму для знаходження факторіала:
#include <iostream>
using namespace std;
long fact1( int k ) {
if( k < 0 ) return 0;
if( k == 0 ) return 1;
return k * fact1( k - 1 );
}
long fact2( int k ) {
if ( k < 0 ) return 0;
int f = 1;
while ( k ) f *= k--;
return f;
}
int main( ) {
cout << fact1( 5 ) << endl;
cout << fact2( 5 ) << endl;
}
Рекурсивними викликами можна замінити циклічні процеси. В наступній програмі рекурсивні функції використовуються для виводу на екран елементів масиву. Перша функція виводить елементи масиву від першого до останнього, друга – від останнього до першого.
#include <iostream>
using namespace std;
void print1( int a[ ], int n ) {
if ( n == 0 ) return;
cout << *a << endl;
print1( a + 1, n - 1 );
}
void print2( int a[ ], int n ) {
if ( n > 1 ) print2( a + 1, n - 1 );
cout << *a << endl;
}
int main( ) {
const int N = 5;
int ar[ N ] = { 1, 2, 3, 4, 5 };
print1( ar, N );
print2( ar, N );
}
Ці функції демонструють важливі властивості рекурсивних функцій: оператори, записані перед рекурсивним викликом, виконуються в тому ж порядку, в якому відбуваються виклики функцій; оператори, розташовані після рекурсивного виклику, виконуються в зворотному порядку відносно рекурсивних викликів даної функції.
Розглянемо функції, призначені для знаходження чисел Фібоначчі.
#include <iostream>
using namespace std;
long knownf[ 47 ];
void init_fibo( ) {
int i;
knownf[ 0 ]=0;
knownf[ 1 ]=1;
for( i = 2; i < 47; i++ )
knownf[ i ] = -1;
} //---------------------------------------------------------------
long fib1( long n ) {
switch ( n ) {
case 0 : return 0; break;
case 1 : return 1; break;
default: return fib1( n – 1 ) + fib1( n – 2 );
}
} //---------------------------------------------------------------
long fib2( long n ){
int i;
if ( knownf[ n ] != -1 )
return knownf[ n ];
else {
knownf[ n ] = fib2( n – 1 )+fib2( n – 2 );
return knownf[ n ];
}
} //---------------------------------------------------------------
void main( ) {
init_fibo( );
cout << fib1( 40 ) << endl;
cout << fib2( 40 ) << endl;
}
При виклику функції fib1(12) буде виконуватись оператор return fib1(11) + fib1(10). Схематичноце можна представити так:
Рис. 11.1. Схема рекурсивних викликів для знаходження 12го числа Фібоначчі
Недоліком цієї функції є те, що знаходження більшості чисел Фібоначчі буде виконуватися декілька разів при кожному виклику функції. Цього можна позбутися, якщо зберігати знайдені числа Фібоначчі в окремому масиві, як це зроблено в функції fib2.
1.66. Класи пам'яті даних. Клас пам'яті, час існування і видимість об’єкта
Кожен об’єкт програми (змінна, константа, функція) має свій тип і клас пам'яті. Тип визначає обсяг пам'яті, який виділяється для даного об’єкта, і операції, що можуть виконуватися над цим об’єктом. Клас пам'яті задає: 1) місце розташування об’єкта в оперативній пам'яті; 2) час існування об’єкта – це час, протягом якого об’єкт зберігається в оперативній пам'яті; 3) область видимості, яка визначає ту частину програми, де можна використовувати цей об’єкт.
На відміну від типу, який завжди треба задавати явно, клас пам'яті можна явно не вказувати, тоді він встановлюється компілятором автоматично за місцем оголошення об’єкта в програмі. В усіх наведених раніше програмах використовувалось автоматичне встановлення класу пам'яті.
За часом існування (або часом життя) об’єкти поділяють на три групи: 1) глобальні (або статичні) – існують протягом усього часу виконання програми; 2) локальні – пам’ять для таких об’єктів виділяється з входом у блок, де вони оголошені, коли завершується виконання блоку, ці об’єкти стають невизначеними, пам’ять, яку вони займали, вважається вільною; 3) динамічні – пам’ять для таких об’єктів виділяється і звільняється за відповідною вимогою програми.
Глобальні та статичні дані зберігаються в окремій області оперативної пам'яті, яку в системах з сегментною організацією пам'яті називають сегментом даних. Локальні дані зберігаються в області пам'яті, що називається стеком. динамічні дані – в області пам'яті, що підлягає динамічному розподілу.
Класи пам'яті об’єктів пов’язані з поняттям програмного блоку. Блоком в С++ вважається тіло функції, а також кожна внутрішня група описів та операторів у фігурних дужках. За правилами замовчування змінні, описані всередині блоку, та формальні параметри функцій мають локальний час існування, а змінні, описані зовні всіх блоків, тобто між функціями, мають глобальний час існування. Відповідно говорять про внутрішні (локальні) і зовнішні (глобальні) оголошення об’єктів програми.
Функції можна описувати тільки на зовнішньому рівні, тому всі функції мають глобальний час існування.
За областю видимості (або областю дії) об’єкти також ділять на три групи: 1) глобальні – видимі в межах усієї програми; 2) частково глобальні – видимі в межах одного програмного файлу; 3) локальні – видимі в блоці, де оголошено даний об’єкт.
