У попа була собака, він її любив.
Вона з'їла шматок м'яса, він її убив.
Убив, закопав, на могилі написав:
" У попа була собака, він її любив...
Рекурсія - це прийом програмування, при використанні якого програма викликає саму себе або безпосередньо або опосередковано.
Спрощення коду – деякі алгоритми легше реалізувати рекурсивно, ніж ітеративно.
Зменшення необхідності в додаткових структурах даних – наприклад, при рекурсивному обході графа можна не використовувати явний стек.
Природне розбиття задачі – якщо задачу можна поділити на підзадачі того ж типу, рекурсія є гарним підходом (наприклад, алгоритм швидкого сортування, пошук у дереві).
Зручність для роботи з деревоподібними структурами – наприклад, HTML-дерево, файлові системи, деревоподібні бази даних.
У теорії алгоритмів є теорема, яка говорить про те, що рекурсія та ітерація є еквівалентними. Це означає, що будь-який алгоритм, який можна реалізувати рекурсивно, з таким самим успіхом може бути реалізований і ітеративно, і навпаки. Може, справді, не варто витрачати час і сили, а використовувати лише цикли?
Тут необхідно розуміти те, що теорія та практика не завжди збігаються. Те, що будь-яку рекурсію можна замінити ітерацією, зовсім не означає, що цей ітераційний код буде компактним, зрозумілим і робочим.
Існує безліч завдань, для яких саме рекурсивне рішення є оптимальним. Наприклад, алгоритми швидкого сортування, роботи з деревами, побудови фракталів, обходу графів та багато інших. Саме в них рекурсія показує свою міць, випереджаючи будь-які інші реалізації за швидкістю роботи та компактністю коду.
Але застосування рекурсії не завжди виправдано.
Є дуже багато прикладів, у яких застосування рекурсії просто марнотратно і не витримує жодної конкуренції з ітерацією. До таких прикладів можна віднести і завдання, яких зазвичай і пояснюють роботу рекурсивних алгоритмів.
Зазвичай завдання, у яких використання рекурсії має сенс, далеко ще не тривіальними. У них часто необхідно використовувати такий прийом, як розбиття завдання на прості кроки, кожен із яких також можна розкласти на дрібніші кроки і так далі, поки не дістанемося найпростіших «кроків». Такі завдання не під силу більшості учнів, і знайомство з рекурсією, як на мене, є доцільним лише на заняттях з високомотивованими дітьми, під час підготовки до олімпіад та конкурсів з інформатики.
'------------------------
'Функція очистки каталога
'------------------------
Function Delete_SubFolder(strFolder)
On Error Resume Next
Set Folder1 = FSO.GetFolder(strFolder)
If Folder1.Files.Count > 0 Then
For Each File In Folder1.Files
File.Delete (vbTrue)
Next
End If
If Folder1.SubFolders.Count > 0 Then
For Each SubFolder In Folder1.SubFolders
If Not (Left(SubFolder.Name, 2) = "!_" And Right(SubFolder.Name, 2) = "_!") Then
SubFolder.Delete (vbTrue)
Else
Delete_SubFolder (SubFolder.Path)
End If
Next
End If
End Function
Ви, напевно, вже помітили схожість понять рекурсії та математичної індукції. У рекурсії, як і в математичної індукції є база — аргументи, для яких значення функції визначені (елементарні задачі), і крок рекурсії - спосіб зведення задачі до більш простих.
У рекурсії кожен виклик функції розбивається на два ключові компоненти:
Базовий випадок (base case) – це умова, при якій рекурсія припиняється. Без нього функція буде викликати саму себе нескінченно, що призведе до помилки переповнення стеку.
Рекурсивний випадок (recursive case) – це частина функції, яка містить рекурсивний виклик, що розбиває задачу на менші підзадачі.
Рекурсія працює за принципом розділяй і володарюй: складна задача розбивається на підзадачі того ж типу, доки не буде досягнуто базового випадку.
Механізм роботи рекурсії:
Функція викликає саму себе з меншими або спрощеними аргументами.
Кожен виклик відкладається у стек викликів .
Доки не буде досягнуто базовий випадок, функція продовжує викликати сама себе.
Коли досягається базовий випадок, виклики починають завершуватися в зворотному порядку (як у стеку).
Існує кілька типів рекурсії, які можна використовувати в програмуванні:
Хвостова рекурсія.
Це форма рекурсії, за якої базовий виклик є останньою операцією у функції перед її поверненням.
Взаємна рекурсія.
Це форма рекурсії, за якої дві або більше функцій викликають одна одну по черзі. Це можна використовувати для алгоритмів пошуку шляху та їм подібних.
Нескінченна рекурсія.
Це форма рекурсії, за якої функція нескінченно викликає сама себе, не досягаючи умови завершення.
Рекурсивні структури даних.
Це форма рекурсії, за якої структура даних, наприклад, дерево або список, звертаються до себе самих.
Мемоїзація.
Це рекурсивний метод, під час якого кешуються минулі результати та їхнє повернення замість повторного обчислення.