Java Month: беріть участь в подіях та отримайте можливість виграти суперприз! 🎁
Дізнатися більше
17.05.2023
11 хвилин читання

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

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

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

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

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

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

  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..

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

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

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

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

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

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

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

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

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

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

FAQ
Що можна використовувати замість рекурсії?

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

Чому рекурсивні алгоритми працюють повільніше?

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

Як оптимізувати рекурсію в програмі?

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

Як працює рекурсія в програмуванні?

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

Що таке базовий випадок у рекурсії та чому він важливий?

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

Яка різниця між прямою та непрямою рекурсією?

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

Ставте в коментарях запитання про рекурсію в програмуванні. На найцікавіші я відповім у моєму Ютуб-каналі.

Сергій Немчинський
CEO FOXMINDED
Додати коментар

Ваш імейл не буде опубліковано. Обов'язкові поля відзначені *

Зберегти моє ім'я, імейл та адресу сайту у цьому браузері для майбутніх коментарів