Як працює рекурсія функції: на прикладі Python

Дмитро Жаріков

programming

Аудіо доріжка

4463

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

Йдеться про рекурсію функції!

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

Рекомендуємо статтю до ознайомлення тим, хто вибрав для себе курс Wezom Академії "Основи Python з нуля до функціонального проекту" і хоче глибше поринути у тему. Тому давайте без зайвих передмов розпочнемо розгляд.

Що таке рекурсія: швидке нагадування

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

Для початку пропонуємо вам поглянути на лист папороті:

Що ви бачите?

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

Ще один схожий приклад - капуста романеско:

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

Але як взагалі листя папороті чи капуста романеско в'яжеться із програмуванням? Давайте розумітися!

Що таке рекурсія функції

Як ми й сказали, рекурсивна функція – це функція, що викликає саму себе.

Подивимося більш «життєвому» прикладі, як може працювати у програмуванні.

Уявіть, що вам потрібно потрапити в вбиральню, яка закрита на ключ. Поряд з гардеробною стоїть коробка, на якій написано, що ключ усередині. Ви відкриваєте коробку, а всередині ще лежать коробки. А в них ще. Як вам діяти, щоб максимально швидко знайти потрібну коробку із ключем?

За великим рахунком, є два алгоритми дій:

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

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

У цьому прикладі summa(1) – це 1, summa(2) – це 2 + summa(1) і так далі. Даний алгоритм простіше буде зрозуміти на наступній схемі:

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

Умови рекурсивних алгоритмів

Продовжимо розглядати наш приклад із summa(n). Є дві найважливіші вимоги, без дотримання яких алгоритм не працюватиме:

Базовий випадок

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

Рекурсія

Щоб базовий випадок у принципі відбувся, потрібна передача змінених даних кожної нової функції. У прикладі перший виклик n = 5, другий — 4 тощо. І лише коли n стає рівним 1, рекурсія завершується.

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

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

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

Розглянемо рекурсивну функцію з прикладу summa(5). У комп'ютері зберігаються дані про функції у вигляді блоку, в якому в свою чергу встановлено значення змінної n та код, який виконується. Наочно це виглядає так:

За виконання функції summa(5) починає викликати summa(4). У цей час формується новий блок і розміщується над попереднім:

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

Далі summa(1) повертає одиницю, завершує роботу та виходить із стека. У верхній частині залишається summa(2):

Тепер summa(2) продовжує виконання з того моменту, на якому зупинилася. За нею - summa (3) і так далі до завершення стека.

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

І тут важливо згадати особливості Python — обмеження стека в 1 000 викликів. Якщо кількість дзвінків виявиться більшою, а ви спробуєте додати ще одну функцію, то отримаєте відповідну помилку - "Переповнення стека". Це обмеження дуже важливо пам'ятати, якщо ви працюєте з Python в цілому і з рекурсією функції зокрема.

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

Ось тут у вас може виникнути логічне питання:«А чи взагалі потрібно використовувати рекурсію функції в Python, якщо по суті того ж результату можна досягти і ітеративними алгоритмами?». Питання абсолютно резонне!

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

Але!

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

З іншого боку, написання ітеративних функцій — це найчастіше громіздкіший і складніший код. Погляньте, як виглядає ітеративна функція для обчислення факторіалу (числа, помноженого на попереднє число):

А ось так виглядає рекурсивна функція:

Різниця очевидна, чи не так?