Що таке рекурсія та рекурсивний метод?

Поняття рекурсії не є виключно комп’ютерним терміном і має природнє походження.  

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

Приклади рекурсії 

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

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

Рекурсія знайшла широке застосування у комп’ютерних науках для вирішення задач, які потребують багаторазового повторення якоїсь дії з накопиченням результату. Наприклад, для підрахунку факторіалу, ми можему створити таку функцію, яка буде викликати всередені саму себе з новими аргументами. Ключовою особливістю застосування рекурсії в програмуванні є правило досяжності — будь-яка рекурсивна функція повинна містити в собі досяжну умову виходу з рекурсії. У випадку відсутності такої умови, функція виконуватиметься нескінченно, а у випадку використання рекурсивного процесу (з відкладеними обчисленнями), ми отримаємо переповнення стеку — для нас це означатиме, що додаток впаде і вже нічого не можна буде вдіяти. 

Існує два основних процеси, в яких може бути застосована рекурсія. Такі процеси називаються рекурсивним та ітеративним. 

Що таке рекурсивний процес?  

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

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

Приклад 

Припустимо, ми хочемо обчислити факторіал числа 5. Факторіал обчислюється для всіх невід’ємних чисел. Таким чином, ми будемо послідовно розкривати по одному множнику до тих пір, поки не досягнемо умови виходу з рекурсивного циклу. Умовою виходу з рекурсивного циклу в даному випадку буде досягненням останнім множником, що є факторіалом, значення нуль, тобто операція обчислення факторіала для нуля буде останньою для рекурсії. Це виглядатиме наступним чином:  

5! = 5 × 4! => 

5 × 4 × 3! => 

5 × 4 × 3 × 2! => 

5 × 4 × 3 × 2 × 1! => 

5 × 4 × 3 × 2 × 1 × 0! => 

5 × 4 × 3 × 2 × 1 × 1 

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

З рекурсивним зрозуміло, а як щодо ітеративного процесу? 

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

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

5! = 5 × 4! => // На цьому кроці у нас з’являється акумулятор, рівний 5 

20 × 3! => // Обчислюємо проміжний результат, який дорівнює 20 

60 × 2! => // Продовжуємо перераховувати проміжний результат... 

120 × 1! => // Продовжуємо перераховувати проміжний результат... 

120 × 0! => // Продовжуємо перераховувати проміжний результат... 

120 // Ми досягли термінальної умови, зупиняємося.  

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

У підсумку 

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

P.S. Якщо ця стаття була для вас корисною, ставте ❤ і поділіться нею з друзями! 😊