Материал: Лекція 3. Рекурсія

6

Лекція 3. Рекурсія

3.1. Поняття рекурсії

3.2. Прості рекурсивні алгоритми

3.2.1. Алгоритм знаходження n!

3.2.2. Алгоритм знаходження чисел Фібоначчі

3.3. Рекурсивні алгоритми обернення рядка

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

3.1. Поняття рекурсії

Неформально, рекурсія — це спосіб загального визначення множини об'єктів або функцій через себе, з використанням раніше заданих окремих визначень.

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

У програмуванні під рекурсією розуміють таку реалізацію, в якій метод використовує у своєму тілі виклик самого себе. Такі виклики називають рекурсивними. Якщо метод A у своєму тілі викликає тільки один рекурсивний метод, то говорять про пряму рекурсію. Під непрямою рекурсією розуміють явище, коли рекурсивні методи викликають один одного (наприклад, метод А викликає B, а метод B викликає A).

Рекурсивні алгоритми складніше налагоджувати, але іноді вони дозволяють дуже гнучко і красиво вирішити завдання.

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

Таким чином, ми можемо говорити про два типи алгоритмів:

1. ітераційні;

2. рекурсивні.

Багато корисних алгоритмів мають рекурсивну структуру: для вирішення завдання вони рекурсивно викликають самі себе один або кілька разів, аби вирішити допоміжне завдання, що має безпосереднє відношення до поставленого завдання. Такі алгоритми часто розробляються за допомогою методу декомпозиції, або розбиття: складне завдання розбивається на декілька простіших, які подібні до початкового завдання, але мають менший об'єм; далі ці допоміжні завдання вирішуються рекурсивним методом, після чого отримані рішення комбінуються з метою отримати рішення початкової задачі.

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

Кількість звернень, виконаних методом без повернення в основну частину називається глибиною рекурсії.

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

Таким чином, кожний рекурсивний метод складається з двох частин:

- базового випадку;

- рекурсивного випадку.

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

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

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

- в системному стеку виділяється пам'ять для нових локальних змінних і параметрів (це називається стеком викликів);

- програмний код методу виконується спочатку з новими локальними змінними і параметрами. Ці локальні змінні і параметри отримують нові початкові значення. Сам програмний код методу не копіюється;

- при поверненні з рекурсивного методу (оператор return) відбувається відновлення старих локальних змінних і параметрів а також їх значень в точці виклику цього методу.

3.2. Приклади рекурсивних алгоритмів

Приклад 1. Рекурсивний метод Countdown(5) виводить на консоль послідовність чисел від 5 до 0.

class Program

{

public static void Main(string[] args)

{

Countdown(5);

Console.ReadKey();

}

private static void Countdown(int i)

{

Console.WriteLine(i);

// базовий випадок

if (i <= 0) return;

// рекурсивний випадок

Countdown(i - 1);

}

}

Як видно з прикладу, метод CountDown викликає сам себе до тих пір, поки змінна i не стане <=0. Зверніть увагу, що циклу в цьому методі немає.

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

1. Обчислення факторіала N!

, де

2. Обчислення чисел Фібоначчі, що задається формулами:

F(1)=1,F(2)=1;F(3)=2, F(n+1)=F(n)+F(n-1)

Приклад 2. Знаходження факторіалу цілого числа

public class Program

{

//Рекурсивний алгоритм

public static long factorial(int n)

{

if (n <= 1) return 1; //базовий випадок

else return n * factorial(n - 1); //рекурсивний

} //factorial

//Не рекурсивний алгоритм

public static long fact(int n)

{

long res = 1;

for (int i = 2; i <= n; i++) res *= i;

return (res);

} //fact

Знаходження чисел Фібоначчі

Числа Фібоначчи — елементи числової послідовності

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946

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

F(1)=1,F(2)=1;F(3)=2, F(n+1)=F(n)+F(n-1)

Простий нерекурсивний алгоритм генерації чисел Фібоначчі розглядався у лекції 2:

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

Приклад 4. Нерекурсивний алгоритм на мові C#

static void Main(string[] args)

{

int a = 1;

int b = 1;

int c = 0;

Console.WriteLine("Введіть кількість чисел послідовності");

int n = int.Parse(Console.ReadLine());

Console.WriteLine("Перше число = " + a);

Console.WriteLine("Друге число = " + b);

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

{

c = a + b;

Console.WriteLine("Наступний член ряду= " + c);

a = b;

b = c;

}

Console.ReadKey();

}

Рекурсивний алгоритм на мові С#

namespace Recursia

{

class Program

{

static int fibon(int i)

{

if (i == 0) return 1; //базовий випадок

if (i == 1) return 1; // базовий випадок

if (i < 0) return 0; // базовий випадок

return fibon(i - 2) + fibon(i - 1); //рекурсивний випадок

}

static void Main(string[] args)

{

int f;

Console.WriteLine("Введіть n");

int i = int.Parse(Console.ReadLine());

f = fibon(i);

Console.WriteLine("Fibonnachi is " + f);

Console.ReadKey();

}

}

}

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

3.3 Рекурсивні алгоритми обернення рядка

Нижче наведений ще один приклад рекурсії для виведення символьного рядка в зворотному порядку. Цей рядок задається як аргумент рекурсивного методу DisplayRev().

Приклад 5.

class RevStr

{

// Обернути рядок

public void DisplayRev(string str)

{

if (str.Length > 0)

DisplayRev(str.Substring(1, str.Length - 1)); //рекурсивний

else

return; //базовий випадок

Console.Write(str[0]);

}

}

class Program

{

static void Main()

{

string s = "Это тест";

RevStr rsOb = new RevStr();

Console.WriteLine("Исходная строка: " + s);

Console.Write("Перевернутая строка: ");

rsOb.DisplayRev(s);

Console.WriteLine();

Console.ReadKey();

}

}

}

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

Можна реалізувати іншу версію алгоритму обернення рядка.

Приклад 6. Алгоритм 2 обернення рядка

https://www.bestprog.net/ru/2019/01/21/recursion-examples-of-recursive-methods-functions-in-c-ru/

class Program

{

static string RString(string s1, int pos)

{

if (pos < s1.Length)

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

else

return ""; // пройдена вся строка - окончание рекурсивного процесса

}

static void Main(string[] args)

{

string s;

s = RString("abcd", 0); // s = "dcba"

Console.WriteLine(s);

s = RString("A", 0); // s = "A"

Console.WriteLine(s);

s = RString("", 0); // s = ""

Console.WriteLine(s);

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

Console.WriteLine(s);

Console.ReadKey();

}

}

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

Переваги:

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

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

Недоліки:

- для заданого алгоритму рекурсивні виклики працюють повільніше ніж ітераційні. Це пов'язано з додатковими витратами системних ресурсів на неодноразові виклики методів;

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

Контрольні запитання і завдання для самостійного виконання