Рекурсія на олімпіаді

Навіщо потрібна рекурсія в програмуванні?

1. Спрощення коду – деякі алгоритми легше реалізувати рекурсивно, ніж ітеративно. 

2. Зменшення необхідності в додаткових структурах даних – наприклад, при рекурсивному обході графа можна не використовувати явний стек.

3. Природне розбиття задачі – якщо задачу можна поділити на підзадачі того ж типу, рекурсія є гарним підходом (наприклад, алгоритм швидкого сортування, пошук у дереві).

4. Зручність для роботи з деревоподібними структурами – наприклад, HTML-дерево, файлові системи, деревоподібні бази даних.

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

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

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

Але застосування рекурсії не завжди виправдано. 

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

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

Як працює рекурсія?

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

Механізм роботи рекурсії:

1. Функція викликає саму себе з меншими або спрощеними аргументами.

2. Кожен виклик відкладається у стек викликів .

3. Доки не буде досягнуто базовий випадок, функція продовжує викликати сама себе.

4. Коли досягається базовий випадок, виклики починають завершуватися в зворотному порядку (як у стеку).