Рекурсія в програмуванні та як її застосовувати

Рекурсія – це повторення шаблону з невеликими змінами. Навколо нас безліч прикладів рекурсії, починаючи з вікон готичного собору, закінчуючи суцвіттям капусти. Але нас цікавить, що таке рекурсія в програмуванні, коли її треба застосовувати, і які в неї недоліки.

Визначення рекурсії в програмуванні

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

Види рекурсії

Існує кілька типів рекурсії, які можна використовувати в програмуванні:

1. Хвостова рекурсія. Це форма рекурсії, за якої рекурсивний виклик є останньою операцією у функції перед її поверненням.
2. Взаємна рекурсія. Це форма рекурсії, за якої дві або більше функцій викликають одна одну по черзі. Це можна використовувати для алгоритмів пошуку шляху та їм подібних.
3. Нескінченна рекурсія. Це форма рекурсії, за якої функція нескінченно викликає сама себе, не досягаючи умови завершення.
4. Рекурсивні структури даних. Це форма рекурсії, за якої структура даних, наприклад, дерево або список, звертаються до себе самих.
5. Мемоїзація. Це рекурсивний метод, під час якого кешуються минулі результати та їхнє повернення замість повторного обчислення.

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

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

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

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

Прикладом рекурсивного алгоритму в програмуванні може бути ряд Фібоначчі, що являє собою послідовність чисел, де кожне число є сумою двох попередніх чисел. Формула для цієї послідовності: F(n) = F(n-1) + F(n-2), а перші два числа в послідовності дорівнюють 0 і 1. Рекурсивний алгоритм для обчислення n-го числа в послідовності Фібоначчі може виглядати так у Python:

“`python

def fibonacci(n):

if n <= 0:

     return 0

elif n == 1:

     return 1

else:

     return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(5)) # Output: 13

“`

У цьому прикладі функція Фібоначчі приймає як параметр ціле число n, яке є n-м числом у послідовності. Функція спочатку перевіряє базові випадки, де n = 0 або n = 1. Якщо n менше або дорівнює 0, вона повертає 0, а якщо n дорівнює 1, вона повертає 1. Якщо n більше 1, функція рекурсивно викликає себе з параметрами n-1 і n-2, а потім повертає суму двох результатів. Рекурсивні виклики функцій вкладені один в одного доти, доки не буде виконано умову завершення.

Базовий випадок і рекурсивний випадок

Базовий випадок – це коли проблема або умова досить прості, щоб їх можна було вирішити без рекурсії.

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

Ідея рекурсії полягає в тому, щоб розбити складну проблему на простіші, поки не буде досягнуто базового випадку. Щойно базовий випадок розв’язано, результат передається назад деревом рекурсії як розв’язання вихідної проблеми.

Стек викликів

Стек викликів, також відомий як стек виконання або просто стек, – це структура даних, у якій зберігається інформація про виклики підпрограм у комп’ютерній програмі. Щоразу, коли викликається функція або метод, контекст виклику поміщається в стек.  

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

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

У цього методу є свої плюси і мінуси. Розберемо їх далі.

Переваги рекурсії

• Стислість і зрозумілість коду.
• Висока продуктивність на рекурсивних завданнях.
• Ефективність використання пам’яті.
• Функціональне програмування за допомогою рекурсій.
• Простота використання.

Недоліки рекурсії

• Можливість переповнення стека.
• Низька продуктивність на багаторівневих завданнях.
• Складніша реалізація.
• Неуніверсальність застосування.
• Підходить не для всіх мов програмування.
• Підходить не для всіх середовищ через можливі проблеми з пам’яттю.

Коли варто використовувати рекурсію, а коли не варто

Коли використовувати рекурсію:

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

Коли не треба використовувати рекурсію:

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

Рекурсія в різних мовах програмування

Рекурсія – це поняття, що існує в більшості мов програмування, і кожна з них має свою специфіку та можливості. Деякі з мов, що підтримують рекурсію, – це Java, Python, JavaScript, C#, PHP, Ruby, Rust, Clojure та інші. У цих мовах функції можуть викликати самі себе і рекурсивно розв’язувати проблеми.

Рекурсія в мові Python

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

Найпоширеніший спосіб використання рекурсії в Python – це використання функцій, які рекурсивно викликають самі себе. Наприклад, функція, яка має обчислювати факторіал чисел, приймає один параметр (число). Функція викликається рекурсивно доти, доки не буде досягнуто число, менше або рівне 1, після чого вона повертає свій результат.

Рекурсія в мові Java

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

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

Рекурсія в мові C++

Рекурсія також підтримується в мові програмування C++ для вирішення найрізноманітніших завдань.

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

Рекурсія у функціональних мовах програмування

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

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

Рекурсія широко використовується в інших мовах функціонального програмування, включно з Lisp, Scheme, Clojure, F#, OCaml, Standard ML та Erlang..

Як перервати рекурсію

У деяких випадках рекурсія зупиняється при досягненні базового випадку або сценарію, за якого функція більше не викликається. Це дає змогу програмі завершити роботу і повернути результат.

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

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

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

Що вибрати: рекурсію чи цикл

Використовувати рекурсію рекомендується, коли розв’язувана проблема природно рекурсивна за своєю природою, наприклад, дерево пошуку або обчислення факторіалу

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

На закінчення

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