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

Що таке дерево рекурсії?

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

Деревоподібна структура

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

Базовий випадок

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

Рекурсивні виклики

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

Потік виконання:

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

Аналіз складності часу

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

вступ

• Подумайте про програму, яка визначає факториал числа. Ця функція приймає число N як вхідні дані та повертає факториал N як результат. Псевдокод цієї функції нагадуватиме,

 // find factorial of a number factorial(n) { // Base case if n is less than 2: // Factorial of 0, 1 is 1 return n // Recursive step return n * factorial(n-1); // Factorial of 5 => 5 * Factorial(4)... } /* How function calls are made, Factorial(5) [ 120 ] | 5 * Factorial(4) ==> 120 | 4. * Factorial(3) ==> 24 | 3 * Factorial(2) ==> 6 | 2 * Factorial(1) ==> 2 | 1 */ 

• Прикладом рекурсії є функція, згадана раніше. Ми викликаємо функцію, щоб визначити факториал числа. Потім, маючи менше значення того самого числа, ця функція викликає сама себе. Це продовжується до тих пір, поки ми не досягнемо основного випадку, в якому більше немає викликів функцій.
• Рекурсія — це техніка обробки складних проблем, коли результат залежить від результатів менших екземплярів тієї самої проблеми.
• Якщо ми думаємо про функції, то функція називається рекурсивною, якщо вона продовжує викликати саму себе, доки не досягне базового випадку.
• Будь-яка рекурсивна функція має два основні компоненти: базовий варіант і рекурсивний крок. Ми перестаємо переходити до рекурсивної фази, коли досягаємо основного випадку. Щоб запобігти нескінченній рекурсії, базові випадки повинні бути правильно визначені та є вирішальними. Визначення нескінченної рекурсії - це рекурсія, яка ніколи не досягає базового випадку. Якщо програма ніколи не досягає базового сценарію, переповнення стека продовжуватиме відбуватися.

Типи рекурсії

Загалом, існує дві різні форми рекурсії:

• Лінійна рекурсія
• Рекурсія дерева
• Лінійна рекурсія

Лінійна рекурсія

• Функція, яка викликає саму себе лише один раз під час кожного виконання, називається лінійно рекурсивною. Гарною ілюстрацією лінійної рекурсії є факторіальна функція. Назва «лінійна рекурсія» стосується того факту, що для виконання лінійно-рекурсивної функції потрібен лінійний час.
• Подивіться на псевдокод нижче:

 function doSomething(n) { // base case to stop recursion if nis 0: return // here is some instructions // recursive step doSomething(n-1); } 

• Якщо ми подивимося на функцію doSomething(n), то вона приймає параметр з іменем n і виконує деякі обчислення перед повторним викликом тієї ж процедури, але з меншими значеннями.
• Коли метод doSomething() викликається зі значенням аргументу n, припустимо, що T(n) представляє загальний час, необхідний для завершення обчислення. Для цього ми також можемо сформулювати рекурентне співвідношення, T(n) = T(n-1) + K. K тут виступає константою. Константу K включено, оскільки функції потрібен час, щоб виділити або звільнити пам’ять для змінної або виконати математичну операцію. Ми використовуємо K, щоб визначити час, оскільки він дуже маленький і незначний.
• Часову складність цієї рекурсивної програми можна просто обчислити, оскільки в найгіршому сценарії метод doSomething() викликається n разів. Формально кажучи, часова складність функції дорівнює O(N).

Рекурсія дерева

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

 function doSomething(n) { // base case to stop recursion if n is less than 2: return n; // here is some instructions // recursive step return doSomething(n-1) + doSomething(n-2); } 

• Єдина відмінність між цим кодом і попереднім полягає в тому, що цей виконує ще один виклик тієї ж функції з меншим значенням n.
• Покладемо T(n) = T(n-1) + T(n-2) + k як рекурентне співвідношення для цієї функції. K знову виступає константою.
• Коли виконується більше ніж один виклик однієї функції з меншими значеннями, такий вид рекурсії відомий як рекурсія дерева. Зараз цікавий аспект: наскільки ця функція займає багато часу?
• Зробіть припущення на основі дерева рекурсії нижче для тієї самої функції.
  
• Вам може здатися, що важко оцінити часову складність, дивлячись безпосередньо на рекурсивну функцію, особливо коли це рекурсія дерева. Метод дерева рекурсії є одним із кількох методів обчислення часової складності таких функцій. Давайте розглянемо його більш детально.

Що таке метод дерева рекурсії?

• Рекурентні співвідношення, такі як T(N) = T(N/2) + N, або два, які ми розглянули раніше в розділі про види рекурсії, розв’язуються за допомогою підходу дерева рекурсії. Ці повторювані відносини часто використовують стратегію «розділяй і володарюй» для вирішення проблем.
• Щоб інтегрувати відповіді на менші підпроблеми, які виникають, коли більшу проблему розбивають на менші підпроблеми, потрібен час.
• Наприклад, відношення повторення T(N) = 2 * T(N/2) + O(N) для сортування злиттям. Час, необхідний для об’єднання відповідей на дві підпроблеми із загальним розміром T(N/2) дорівнює O(N), що також справедливо на рівні реалізації.
• Наприклад, оскільки рекурентне відношення для двійкового пошуку дорівнює T(N) = T(N/2) + 1, ми знаємо, що кожна ітерація двійкового пошуку призводить до простору пошуку, розрізаного навпіл. Після визначення результату ми виходимо з функції. Відношення повторення має +1, оскільки це операція з постійним часом.
• Слід розглянути рекурентне співвідношення T(n) = 2T(n/2) + Kn. Kn означає час, необхідний для комбінування відповідей на n/2-вимірні підпроблеми.
• Давайте зобразимо дерево рекурсії для вищезгаданого рекурентного відношення.

Ми можемо зробити кілька висновків, вивчивши дерево рекурсії вище

1. Величина проблеми на кожному рівні – це все, що має значення для визначення вартості вузла. Розмір випуску становить n на рівні 0, n/2 на рівні 1, n/2 на рівні 2 і так далі.

2. Загалом, ми визначаємо висоту дерева як рівну log (n), де n — розмір проблеми, а висота цього дерева рекурсії дорівнює кількості рівнів у дереві. Це правда, тому що, як ми щойно з’ясували, стратегія «розділяй і володарюй» використовується рекурентними відносинами для вирішення проблем, а для переходу від розміру проблеми n до розміру проблеми 1 просто потрібно зробити log (n) кроків.

• Розглянемо, наприклад, значення N = 16. Якщо нам дозволено ділити N на 2 на кожному кроці, скільки кроків потрібно зробити, щоб отримати N = 1? Враховуючи, що ми ділимо на два на кожному кроці, правильною відповіддю буде 4, що є значенням log(16) за основою 2.

log(16) з основою 2

log(2^4) основа 2

4 * log(2) за основою 2, оскільки log(a) за основою a = 1

отже, 4 * log(2) основа 2 = 4

3. На кожному рівні другий член у повторенні вважається коренем.

Незважаючи на те, що в назві цієї стратегії є слово «дерево», вам не потрібно бути експертом з дерев, щоб це зрозуміти.

Як використовувати дерево рекурсії для вирішення рекурентних відношень?

Вартість підпроблеми в техніці дерева рекурсії - це кількість часу, необхідного для вирішення підпроблеми. Тому, якщо ви помітили фразу «вартість», пов’язану з деревом рекурсії, вона просто стосується кількості часу, необхідного для вирішення певної підпроблеми.

Давайте розберемо всі ці кроки на кількох прикладах.

приклад

Розглянемо рекурентне співвідношення,

T(n) = 2T(n/2) + K

Рішення

Дане рекурентне співвідношення показує наступні властивості,

Проблема розміром n ділиться на дві підпроблеми розміром n/2 кожна. Вартість об’єднання рішень цих підпроблем становить K.

Кожна проблема розміром n/2 ділиться на дві підпроблеми розміром n/4 і так далі.

if else цикл у java

На останньому рівні розмір підпроблеми буде зменшено до 1. Іншими словами, ми нарешті досягли базового випадку.

Давайте виконаємо кроки, щоб розв’язати це відношення повторення,

Крок 1: Намалюйте дерево рекурсії

Крок 2: Обчисліть висоту дерева

Оскільки ми знаємо, що коли ми безперервно ділимо число на 2, настає момент, коли це число зменшується до 1. Так само, як і з розміром задачі N, припустимо, що після K ділень на 2 N стає рівним 1, що означає, ( n / 2^k) = 1

Тут n / 2^k — це розмір проблеми на останньому рівні, і він завжди дорівнює 1.

Тепер ми можемо легко обчислити значення k із наведеного вище виразу, взявши log() до обох сторін. Нижче наведено більш чітке визначення,

n = 2^k

• log(n) = log(2^k)
• log(n) = k * log(2)
• k = log(n) / log(2)
• k = log(n) за основою 2

Отже, висота дерева дорівнює log (n) за основою 2.

Крок 3: Розрахуйте вартість на кожному рівні

• Вартість на рівні-0 = K, дві підпроблеми об’єднані.
• Вартість на рівні-1 = K + K = 2*K, дві підпроблеми об’єднуються двічі.
• Вартість на рівні-2 = K + K + K + K = 4*K, дві підпроблеми об’єднуються чотири рази. і так далі....

Крок 4: Обчисліть кількість вузлів на кожному рівні

Давайте спочатку визначимо кількість вузлів на останньому рівні. З дерева рекурсії ми можемо це зробити

• Рівень-0 має 1 (2^0) вузол
• Рівень-1 має 2 (2^1) вузли
• Рівень-2 має 4 (2^2) вузли
• Рівень-3 має 8 (2^3) вузлів

Отже, рівень log(n) повинен мати 2^(log(n)) вузлів, тобто n вузлів.

Крок 5: Підсумуйте вартість усіх рівнів

• Загальну вартість можна записати як
• Загальна вартість = Вартість усіх рівнів, крім останнього рівня + Вартість останнього рівня
• Загальна вартість = Вартість рівня-0 + Вартість рівня-1 + Вартість рівня-2 +.... + Вартість рівня-log(n) + Вартість останнього рівня

Вартість останнього рівня обчислюється окремо, оскільки це базовий випадок, і на останньому рівні об’єднання не виконується, тому вартість вирішення однієї проблеми на цьому рівні є деякою постійною величиною. Приймемо це як O (1).

Давайте введемо значення у формули,

• T(n) = K + 2*K + 4*K + .... + log(n)` разів + `O(1) * n
• T(n) = K(1 + 2 + 4 + .... + log(n) разів)' + 'O(n)
• T(n) = K(2^0 + 2^1 + 2^2 + ....+ log(n) разів + O(n)

Якщо ви уважно подивитесь на наведений вище вираз, то він утворює геометричну прогресію (a, ar, ar^2, ar^3 ...... нескінченний час). Сума GP визначається як S(N) = a / (r - 1). Ось перший член, а r — загальне відношення.