Рекурсія. Приклади розв’язку задач. Переваги та недоліки рекурсії

Рекурсія. Приклади розв’язку задач. Переваги та недоліки рекурсії


Зміст


1. Що таке рекурсія? Що називається рекурсією?

У теорії алгоритмів дається наступне визначення рекурсії: рекурсія – це такий спосіб задавання функції, при якому результат повернення з функції для даного значення аргументу визначається на основі результату повернення з тієї ж функції для попереднього (меншого або більшого) значення аргументу.

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

2. Пояснення до реалізації задач на рекурсію. Як правильно організувати рекурсивний виклик функції?

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

Щоб циклічний процес перетворити в рекурсивний, потрібно вміти визначити (виділити) три важливі моменти:

  • умову припинення рекурсивного процесу. Наприклад, якщо лічильник або ітератор з іменем k змінюється від 1 до 10 у зростаючому порядку, то умова припинення є досягнення значення k=10. Умова припинення вказується в операторі return;
  • формулу наступного елементу або ітератору, що використовується в рекурсивному процесі. Ця формула вказується в операторі return;
  • перелік параметрів, що передаються в рекурсивну функцію. Один з параметрів обов’язково є ітератор (лічильник), який змінює своє значення. Інші параметри є додатковими, наприклад, посилання на масив, над яким здійснюється обробка.



3. Пошук суми елементів масиву. Приклад

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

Задача. Задано масив чисел A. Розробити рекурсивну функцію, яка знаходить суму елементів масиву:

S = A[0] + A[1] + … + A[n],

де n – кількість елементів масиву. Програмний код функції наступний:

// рекурсія - сума елементів масиву
static int Sum(int i, int[] A) {
    if (i==(A.length-1))
        return A[i];
    return A[i] + Sum(i+1,A);
}

У вищенаведеному коді функція отримує два параметри. Перший параметр i є значення поточного індексу, який змінює своє значення при кожному рекурсивному виклику. Другий параметр A – масив, елементи якого додаються.

Останній елемент масиву має індекс A.length-1. Досягнення функцією останнього елементу масиву є виходом з неї. Тому, в тексті функції Sum() вказується умова припинення рекурсивного процесу:

if (i==(A.length-1))
    return A[i];

У мові Java масив є екземпляром (об’єктом) класу, тому кількість елементів у масиві визначається властивістю length. Це є зручно, оскільки не потрібно передавати розмірність масиву у вигляді параметру (на відміну від інших мов програмування).

Оскільки, здійснюється сумування поточного значення A[i] з наступними, то вказується рядок

// A[i] - поточне значення, Sum(i+1,A) – наступне значення в масиві
return A[i] + Sum(i+1,A);

де Sum(i+1, A) означає наступне значення масиву A, яке буде обчислене на наступному (нижньому) рівні рекурсивного процесу. Параметр i+1 вказує, що на наступному рівні рекурсії буде взято наступний за даним елемент масиву.

Використання функції Sum() в іншому програмному коді може бути таким:

int[] A = { 3, 12, 10, 11 };
int sum;
sum = Sum(0,A); // sum = 36

4. Знаходження факторіалу числа – n!. Приклад

У прикладі розроблено рекурсивну функцію, яка знаходить факторіал заданого числа n

f = 1 · 2 · … · (n-1) · n

де n>=1.

Програмний код функції наступний:

// обчислення факторіалу числа n
int Fact(int n) {
    if (n==1)
        return 1; // умова завершення рекурсивного процесу
    else
        return n*Fact(n-1); // Fact(n-1) - результат наступних викликів функції
}

У даній функції відбувається рекурсивний виклик функції Fact() з параметром n, який змінюється від n до 1 у спадному порядку. Рекурсивний процес завершується, коли n = 1.

При поверненні на рівень вище повертається поточне n та результат обчислень при наступних рекурсивних викликах:

return n*Fact(n-1);

Використання функції в іншому програмному коді:

int fact;        
fact = Fact(7); // fact = 5040

5. Програма знаходження найбільшого спільного дільника (алгоритм Евкліда). Приклад

У прикладі визначається найбільший спільний дільник за формулою Евкліда:

Програмний код функції наступний:

// НСД - Алгоритм Евкліда
int MaxDivisor(int n, int m) {
    if (n==m) return n;
    else
        if (n>m) return MaxDivisor(n-m, m);
        else
            return MaxDivisor(n, m-n); // n<m
}

Використання функції MaxDivisor

int md;
md = MaxDivisor(28,20); // md = 4

6. Обчислити n-й член послідовності чисел Фібоначчі. Приклад

Послідовність чисел Фібоначчі має вигляд:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

У послідовності чисел Фібоначчі кожне наступне число n визначається як сума двох попередніх чисел: (n-1) + (n-2). Тому, у формулі рекурсивного процесу має бути виклик суми двох функцій а не однієї. Припинення рекурсивного процесу досягається, коли значення n=0.

Нижче наведено текст функції GetNFibonacci()

// Визначення n-го числа Фібоначчі
static int GetNFibonacci(int n) {
    if (n>1)
        return GetNFibonacci(n-2)+GetNFibonacci(n-1); // формула Фібоначчі
    else
        if (n==1)
            return 1;
        else
            return 0; // якщо n==0
}

Використання методу GetNFibonacci() в іншому програмному коді:

int n;           
n = GetNFibonacci(10); // n = 55

7. Переваги та недоліки рекурсії

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

Можна виділити такі взаємозв‘язані переваги рекурсії:

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

Недоліки рекурсії полягають в наступному:

  • порівняно з ітерацією багаторазовий виклик рекурсивної функції працює довше. Це зв‘язано з тим, що при виклику рекурсивного методу його параметри копіюються в стек. Також запам’ятовуються тимчасові значення локальних внутрішніх змінних. При завершенні виклику рекурсивної функції попередні значення параметрів витягуються зі стеку, що призводить до зайвих операцій. Ітераційний алгоритм для тієї самої задачі працює швидше;
  • для рекурсивного процесу потрібно більше пам‘яті. Це зв‘язано з тим, що при рекурсивному виклику потрібно зберігати попереднє значення внутрішніх змінних викликаючої функції, щоб при завершенні рекурсивного виклику відновити її виконання. Таким чином, якщо рекурсивна функція викликається дуже багато разів, то це може призвести до надмірного використання пам‘яті.


Зв‘язані теми