Рекурсивні функції

Мова С++ підтримує можливість звернення функції самої до себе — рекурсію.Розрізняють пряму і непряму рекурсії. Функція називається прямо рекурсивною, якщо містить у своє­му тілі виклик самої себе. Якщо ж функція викликає іншу функцію, що у свою чергу викликає першу, то така функція називається непрямо рекурсивною.Рекурсивні функції найчастіше використовуються для компактної реалізації рекурсивних алгоритмів.

Класичні приклади використання рекурсії — реалізація операції піднесення до степеня і обчислення факторіала числа. Зазначимо, що ці приклади популярні тільки через їхню зруч­ність для пояснення поняття рекурсії, однак вони не дають ви­грашу в програмній реалізації порівняно з ітераційним спосо­бом розв’язання цих задач.

Розглянемо рекурсивну функцію обчислення факторіала. Для того щоб одержати значення факторіала числа n!, необхід­но помножити на n факторіал числа (n-1)!.Ураховуючи, що 0! = 1 та 1! = 1, наведемо приклад цієї функції:

long fact (long n)

{

return (n>l) ? n * fact (n-1) : 1;

}

Рекурсивні функції є зручним засобом породження комбі­наторних об’єктів заданого виду.

Приклад 9.13. Вивести на екран усі зростаючі послідовності дов­жиною k, елементами яких є натуральні числа від 1 до n. Передбача­ється, що k не перевищує n, інакше таких послідовностей не існує.

Програма буде оперувати з масивом а₀… а_k-1 і цілою змін­ною t. Припускаючи, що а₀… at — зростаюча послідовність на­туральних чисел з відрізку 1…n, рекурсивна функційgenerate() друкує всі її зростаючі продовження до довжини k.

/* Р9_13.СРР — вывести на экран все возрастающие последовательности длиной k, элементами которых являются натуральные числа от 1 до n */

#include <iostream.h>

#include <conio.h>const int m=20;/* максимальная размерность массива возрастающей последовательности */

int t=1, n, k, a[m];/* k — длина возрастающей последовательностиn — длина отрезка натуральных чисел, из которых формируются последовательности*/

/* generate() — рекурсивная функция генерации возрастающих последовательностей */

void generate()

{

int і;

if (t == k)

//одна из последовательностей полностью сформирована

{

// вывод последовательности

for (i = 0; i<k; i++)

cout << a[i] <<' ';

cout << endl;

}

else

//формирование последовательности

{ t++;

for (i = a[t-2] +1; і <= t-k+n; i++)

{ a[t-1] = i;

generate(); // рекурсивный вызов функции generate()

}

t--;

}

}

void main()

{ int j;

cout << "input k, n (k<n)\n k=";

cin >> k;

cout << "n=";

сіn >> n;

cout <<endl;

for (j = 1; j<=n-k+l; j++)

{a[t-1]=j;

generate();

}

getch();

}

Результати:

input k, n (k<n)

k=3

n=5

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

2 3 4

2 3 5

2 4 5

3 4 5

Класичним прикладом використання рекурсії є також швид­ке сортування — один з найефективніших методів сортування.

Загальний алгоритм швидкого сортування здійснюється та­ким чином:

• з масиву вибирається деякий опорний елемент а_і, (частіше — центральний);

• виконується процес розподілу масиву, що переміщує всі елементи, менші або рівні а_і, вліво від нього, а всі елементи, більші або рівні а_і, — вправо;
• тепер масив складається з двох підмасивів, причому лі­вий менше або дорівнює правому:

[medium]http://cpp.dp.ua/uploads/posts/2015-12/1450293027_9_6.png[/medium]

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

Приклад 9.14. Відсортувати одновимірний масив а„ за зростанням елементів, використовуючи рекурсивну функцію швидкого сортування.

У заданому масиві а<,… a_Nend здійснемо розділення його еле­ментів:

• виберемо з масиву центральний елемент с, за яким буде здійснюватися розділ;
• введемо індекси і і j, які на початку алгоритму вказу­ють, відповідно, на лівий та правий елементи заданої послі­довності;
• будемо рухатися одиничним кроком за допомогою індек­су і у напрямку до кінця масиву, поки не знайдемо елемент а_і >= с. Потім аналогічним чином почнемо рухатися за допо­могою індексу j від кінця масиву до початку, доки не знайдемо а_j<=с;
• далі, якщо i<=j, міняємо елементи а_i, a_j місцями і про­довжуємо рухати і та j за тими ж правилами;
• повторюємо попередній крок, доки i<=j.

Роботу рекурсивної функції швидкого сортування для ма­сиву ао…a₆(QuickSortRecur()), що має значення 5, 10, 8, 7, З, 4, 9, з центральним елементом с = а₃можна представити та­ким чином:

Тепер масив розділений на дві частини: всі елементи лівої частини менше або дорівнюють с, усі елементи правої — біль­ше або дорівнюють с. Розподіл завершено. Якщо підмасив, роз­ташований ліворуч або праворуч від с, містить більше одно­го елемента, викликаємо рекурсивну функцію QuickSortRecur() для нього. Програмна реалізація матиме такий вигляд:

/* Р9_14.СРР — отсортировать исходный массив по возрастанию методом быстрой сортировки */

#include <iostream.h>

#include <conio.h>

template <class T>

void QuickSortRecur(T* a, int Nend)

{

// исходный массив a[ ], a[Nend] — его последний элемент

int і = 0, j = Nend;

T rab, с;

с = a[Nend >>1]; /* выбор центрального элемента с использованием операции побитового сдвига вправо */

do

{ while (a[i] < с) i++;

while (a[j] > с) j-; 

if (i<=j) 

{ rab = a[i];   

a[i++] = a[j];   

a[j--] = rab;}

}

while (i <= j);

/* рекурсивные вызовы функции QuickSortRecur(), если есть, что сортировать */ 

if (j > 0) QuickSortRecur(a, j);

if (Nend > i) QuickSortRecur(a+i, Nend-i);

}

void main()

{ int a[] = (2, 7, 6, 9, 45, 4, 3, 67, 104, 1, 99, 72, 43, 8, 4, 28, 100};

int n = sizeof(a)/sizeof(int);

QuickSortRecur(a, n-1);

cout << "\n Result Quick-sortirovki massiva" << endl;

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

cout << a[i] <<' ';

getch();

}

Результати обчислень:

Result Quick-sortirovki massiva

1 2 3 4 4 6 7 8 9 28 43 45 67 72 99 100 104

Кількість кроків розподілу (глибина рекурсії) складає при­близно ln n, якщо масив поділяється на приблизно рівні части­ни. Загальна швидкодія цього методу сортування:n ln n. Та­кож слід зауважити, що швидке сортування не є ефективним для коротких масивів.