C++,Visual C++,Теорія

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

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

Зміст

Пошук на інших ресурсах:

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

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

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

⇑

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

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

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

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

⇑

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

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

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

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

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

// сума елементів масиву
int Sum(int i, int A[], int n)
{
    if (i==n-1)
        return A[i];
    else
        return A[i]+Sum(i+1,A,n);
}

Як видно з прикладу, у рекурсивну функцію Sum() передається 3 параметри:

  • поточне значення ітератора i;
  • масив A;
  • кількість елементів масиву n.

Вихід з функції здійснюється, коли буде оброблено останній елемент масиву. Умова припинення рекурсивного процесу має вигляд:

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

Для сумування поточного значення A[i] з наступними вказується рядок:

return A[i]+Sum(i+1,A,n);

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

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

int A[] = { 5, 7, 2, -1 };
int n = 4;
int sum;
sum = Sum(0,A,n); // sum = 13

⇑

4. Приклад підрахунку кількості входжень заданого символу в рядку

У даному прикладі реалізовано рекурсивну функцію Count(), яка визначає кількість входжень заданого символу c в рядку s. Функція отримує 3 параметри:

  • символ с, який потрібно порівняти з кожним символом рядка s;
  • рядок s;
  • додаткова змінна i, яка є лічильником рекурсивного циклу.

Реалізація функції Count() наступна:

// підрахунок символу c в рядку символів s
int Count(char c, string s, int i)
{
    if (i==s.length()) // умова закінчення рекурсивного процесу - увесь рядок пройдено
        return 0;
    else
    {
        if (c == s[i]) // якщо символ знайдено
            return Count(c,s,i+1)+1; // збільшити кількість знайдених символів на 1
        else
            return Count(c,s,i+1); // інакше, перейти до обробки наступного символу
    }
}

⇑

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

Обчислення факторіалу числа методом рекурсії є майже в кожному підручнику. Факторіал числа обчислюється за формулою

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

де n>=1.

Рекурсивний виклик можна організувати двома способами:

  • в порядку зростання 1, 2, …, n;
  • в порядку спадання n, n-1, …, 2, 1.

У даному прикладі розроблено дві функції, які знаходять факторіал обома способами. Програмний код функцій наступний:

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

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

У першу функцію Fact1() передаються 2 параметри. Перший параметр визначає максимально можливе значення n, яке може бути помножене. Другий параметр визначає поточне значення i яке приймає участь у множенні.

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

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

int f;

// використання функції Fact1()
f = Fact1(5,1); // f = 5! = 120
f = Fact1(7,1); // f = 7! = 5040
f = Fact1(2,1); // f = 2! = 2

// використання функції Fact2()
f = Fact2(5); // f = 5! = 120;
f = Fact2(8); // f = 8! = 40320;

⇑

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

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

Формула Евкліда НСД

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

// найбільший спільний дільник за алгоритмом Евкліда
int MaxDiv(int n, int m)
{
    if (n==m)
        return n;
    else
    if (n>m)
        return MaxDiv(n-m, m);
    else
        return MaxDiv(n, m-n);
}

Використання функції MaxDiv():

int md;
md = MaxDiv(8, 3); // md = 1
md = MaxDiv(24, 96); // md = 24
md = MaxDiv(9, 15); // md = 3

⇑

7. Підрахунок кількості елементів масиву, більших заданого числа. Приклад

Демонструється метод Count(), який повертає кількість елементів, більших заданого числа num. У метод передається 4 параметри:

  • число num, яке потрібно порівнювати з кожним елементом масиву;
  • масив чисел A[ ];
  • кількість елементів масиву n;
  • поточне значення лічильника в масиві.
// підрахунок кількості елементів масиву, більших заданого числа
int Count(double num, double A[], int n, int i)
{
    if (i==n)
        return 0; // умова закінчення рекурсивного процесу
    else
    {
        if (num<A[i])
            return Count(num, A, n, i+1) + 1; // додати 1 до результату
        else
            return Count(num, A, n, i+1);
     }
}

Використання методу Count() в іншому методі

double A[] = { 2.8, 3.5, 1.9, 2.2, 3.6 };
int k;
k = Count(2.3, A, 5, 0); // k = 3
k = Count(0.9, A, 5, 0); // k = 5

⇑

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

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

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

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

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

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

⇑

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

⇑