Рекурсія. Приклади рекурсивних методів (функцій) в C#

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

---

Зміст

• 1. Що таке рекурсія? Що таке рекурсивний метод (функція)?
• 2. Як працює рекурсивний виклик методу?
• 3. Які переваги дає використання рекурсії у програмах?
• 4. Які недоліки використання рекурсії у програмах?
• 5. Приклад обчислення суми ряду
• 6. Приклад конвертування рядка “AAABCCCCAADDDEF” => “3AB4C2A3DEF”
• 7. Приклад порівняння рядків
• 8. Приклад рекурсивної функції реверсування рядка
• 9. Приклад рекурсивної функції визначення, чи рядок симетричний
• Зв’язані теми

---

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

1. Що таке рекурсія? Що таке рекурсивний метод (функція)?

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

Рекурсивний метод – це метод, який сам себе викликає. У рекурсивному методі міститься виклик цього ж методу за його іменем.

Послідовний процес рекурсивних викликів методу є подібний до циклічного процесу.

  ⇑

2. Як працює рекурсивний виклик методу?

Якщо метод викликає сам себе, то в пам’яті відбуваються наступні процеси:

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

  ⇑

3. Які переваги дає використання рекурсії у програмах?

Рекурсія завжди порівнюється з ітерацією. Для багатьох задач, рекурсія дає наступні взаємопов’язані переваги:

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

---

---

  ⇑

4. Які недоліки використання рекурсії у програмах?

Порівняно з ітераційними викликами, побудова рекурсивних викликів має такі недоліки:

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

  ⇑

5. Приклад обчислення суми ряду

Розробити рекурсивну функцію обчислення суми ряду

S = 5 + 10 + 15 + … + 5·n,

якщо n>0.

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

// рекурсивна функція - сума
static int S(int n)
{
    if (n == 1)
        return 5;
    else
        return 5 * n + S(n - 1);
}

  ⇑

6. Приклад конвертування рядка “AAABCCCCAADDDEF” => “3AB4C2A3DEF”

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

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

Рекурсивна функція містить наступні параметри:

• рядок s типу string, який обробляється;
• змінна, що визначає позицію символу в рядку s на даному рівні рекурсії. Символ s[pos] має тип char;
• ціле число k, яке визначає кількість повторень символу s[pos] на даному рівні рекурсії;
• змінна c типу char, яка визначає символ на попередньому рівні рекурсії. Це є необхідно, тому що символи, які зустрічаються один раз підряд мають оброблятись особливо.

// рекурсивна функція обробки рядка
static string ConvertStr(string s, int pos, char c, int k, string s2)
{
  if (pos < s.Length) // поки не останній символ S[pos] - здійснюються рекурсивні виклики
  {
    if (pos == 0) // перший символ рядка
      // перейти до обробки наступного символу
      return ConvertStr(s, pos + 1, s[pos], 1, s2);
    else // не перший символ рядка
    {
      if (s[pos] == c) // якщо наступний і попередній символи співпадають, то рухаємось далі
        return ConvertStr(s, pos + 1, s[pos], k + 1, s2);
      else // якщо символи змінюються, то зафіксувати у рядку s2 тимчасовий результат
      {
        // якщо k==1, то просто додати до s2 символ c,
        // інакше, перед символом c поставити кількість k
        if (k == 1)
          s2 = s2 + c.ToString();
        else
          s2 = s2 + k.ToString() + c.ToString(); // s2 = s2 + "AAA' = s2 + "3A"

        // перейти на наступний рівень рекурсії, з значенням
        return ConvertStr(s, pos + 1, s[pos], 1, s2);
      }
    }
  }
  else // пройдено увесь рядок
  {
    // завершити обробку рядка
    if (k == 1)
      s2 = s2 + c.ToString();
    else
      s2 = s2 + k.ToString() + c.ToString();
    return s2; // закінчення рекурсивного процесу
  }
}

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

string resStr;
string s2 = "";
string s = "AAABCCCCAADDDD";

resStr = ConvertStr(s, 0, ' ', 0, s2); // resStr = "3AB4C2A4D"
resStr = ConvertStr("ACDDVFFSA", 0, '+', 0, ""); // resStr = "AC2DV2FSA"
resStr = ConvertStr("+++---;;;zzxkf", 0, '+', 0, ""); // resStr = "3+3-3;2zxkf"
resStr = ConvertStr("ddd", 0, 'z', 0, ""); // resStr = "3d"

  ⇑

7. Приклад порівняння рядків

Розробити рекурсивну функцію, яка порівнює два рядки на ідентичність. Два рядки вважаються ідентичними, якщо:

• довжина рядків співпадає;
• співпадають символи кожного рядка, які знаходяться на однакових позиціях.

Рекурсивна функція повинна отримувати наступні параметри:

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

Функція повинна повертати результат типу bool. Якщо рядки ідентичні, то функція повертає true, інакше функція повертає false.

// рекурсивна функція порівняння рядків
static bool EqualStrings(string s1, string s2, int pos)
{
  if (s1.Length != s2.Length) // чи рівні довжини рядків?
    return false;
  else
    if (pos < s1.Length)
    {
      // якщо символи в однакових позиціях не співпадають, то false
      // інакше перейти на наступний рівень рекурсії
      if (s1[pos] != s2[pos])
        return false;
      else
        return EqualStrings(s1, s2, pos + 1);
    }
    else
      return true; // пройдено всі символи рядків: рядки рівні
  }

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

bool b;
b = EqualStrings("abc", "abc", 0); // b = true
b = EqualStrings("abc", "abcd", 0); // b = false
b = EqualStrings("AAA", "AAB", 0); // b = false
b = EqualStrings("", "", 0); // b = true

  ⇑

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

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

// реверсування рядка
static string RString(string s1, int pos)
{
  if (pos < s1.Length)
    return s1[s1.Length - pos - 1].ToString() + RString(s1, pos + 1);
  else
    return ""; // пройдено увесь рядок - закінчення рекурсивного процесу
}

У функції RString() визначення останнього символу в рядку відбувається за формулою:

s1[s1.Length - pos - 1]

Потім цей символ переводиться в рядок методом ToString(). Символ рядок додається до наступного (попереднього) символу в рядку з допомогою рекурсивного виклику

s1[s1.Length - pos - 1].ToString() + RString(s1, pos + 1)

Оскільки функція повинна щось повернути, то перед формулою обробки рядка потрібно вкласти оператор return

return s1[s1.Length - pos - 1].ToString() + RString(s1, pos + 1);

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

string s;
s = RString("abcd", 0); // s = "dcba"
s = RString("A", 0); // s = "A"
s = RString("", 0); // s = ""
s = RString("www.bestprog.net", 0); // s = "ten.gorptseb.www"

  ⇑

9. Приклад рекурсивної функції визначення, чи рядок симетричний

Розробити рекурсивну функцію, яка визначає чи є симетричною частина рядка s, починаючи з i-го елементу і закінчуючи j-м елементом

// рекурсивна функція, що визначає, чи є рядок симетричним
// параметр pos зміщення від i до (j-i)/2
static bool IsSymmetric(string s, int i, int j, int pos)
{
  if ( (i + pos) <= ((j - i) / 2))
  {
    if (s[i + pos] != s[j - pos]) // порівняння символів рядка
      return false;
    else
      return IsSymmetric(s, i, j, pos + 1); // розглянути наступні два символи
  }
  else
    return true; // пройдено увесь рядок
}

У вищенаведеній функції порівнюються символи, що розміщуються на позиціях i+pos та j-pos рядка з допомогою оператора if

if (s[i + pos] != s[j - pos])
...

Параметр pos є зміщенням, яке додається до значення i: i+pos. Між позиціями i та j є деякі символи, що формують деякий діапазон. Не потрібно проходити параметром pos увесь діапазон від i до j. Достатньо переглянути тільки половину діапазону, тому функція містить перевірку:

if ( (i + pos) <= ((j - i) / 2))
{
  ...
}

де

((j - i) / 2)

є середина діапазону (j-i) згідно з умовою задачі.

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

bool b;
b = IsSymmetric("abcd", 1, 3, 0); // b = false
b = IsSymmetric("abcdefed", 3, 7, 0); // b = true
b = IsSymmetric("aaaa", 2, 2, 0); // b = true
b = IsSymmetric("aabbccbbaa", 0, 9, 0); // b = true
b = IsSymmetric("aabbcbbaa", 0, 8, 0); // b = true
b = IsSymmetric("aabbccbaa", 0, 8, 0); // b = false

  ⇑

---

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

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

  ⇑

---