Сьогодні ми розглянемо не просту, але дуже важливу тему, для людей, які обрали своєю сферою діяльності програмування.
Мова йде про рекурсію функції!
Ми зробимо все можливе для того, щоб донести до вас цю інформацію максимально доступно. Так що розібратися в поданій нами інформації зможуть і початківці.
Рекурсією у програмуванні називають таку функцію, яка здатна викликати себе з себе ж, але змінюючи значення параметрів. Можливо, поки що це складно усвідомити, тому ми спробуємо поглянути на цю тему зі сторони “побутових” прикладів. Як приклад можемо розглянути лист папороті:
Що ми бачимо?
Ми маємо одну «основну» гілку. З неї розгалужується багато подібних до «основної» гілок, але менші. З яких відходять ще менші гілки.
Тобто, якщо ми сприймаємо «основну» гілку, як функцію, то бачимо, що з неї утворюються подібні функції, тільки параметри в них змінилися. В даній ситуації змінився розмір.
Можливо навести ще один подібний приклад – капуста романеско.
У цілому, природа має багато показових ілюстрацій рекурсії. Це явище часто використовується і в інших видах людської діяльності, таких як живопис, музика, архітектура та інші види мистецтва.
Рекурсія – одночасно хаос і порядок.
Але як взагалі це природне явище поєднується з кодингом та програмуванням? Розберемося!
Як було сказано, рекурсія функції – це функція, яка звертається до самої себе. Звернемо увагу на «життєвий» приклад, який може працювати у програмуванні.
Уявіть, що вам треба зайти у кімнату, яка зачинена. Поруч знаходиться коробка, на котрій вказано, що ключ знаходиться в ній. Відкриваєте коробку і диво — всередині ще коробки. А в них ще коробки. І так буде продовжуватись до певного моменту. Що ж можна зробити аби знайти потрібну коробку з ключем? Для цього існує два методи:
У першому випадку ви застосуєте цикл «while». Тобто ви будете відкривати коробку за коробкою і так поки не відкриєте ту саму потрібну, в якій знаходиться ключ. Цей метод називається ітераційним, або покроковим.
def summa(n):
x = 0
for n in range(1, n+1):
x += n
return x
summa(5)
>>> 15
def summa(n):
if n == 1:
return 1
return n + summa(n-1)
summa(5)
>>> 15
У цьому прикладі summa(1) – це 1, summa(2) – це 2 + summa(1) і так далі. Даний алгоритм простіше буде зрозуміти на наступній схемі:
І тут потрібно звернути увагу на одну важливу деталь. За великим рахунком, обидва алгоритми виконують одне й те саме завдання — шукають «коробку з ключем».
Загалом, обидва алгоритми працюють і виконують потрібне нам завдання – шукають «коробку з ключем». До того ж, у такому випадку метод рекурсії не матиме особливої переваги над ітераційним.
Однак рекурсія функції краще вирішує складні, багаторівневі завдання. Метод рекурсії допоможе виконати їх швидше та зрозуміліше, а ще, що важливо, рішення завдань методом рекурсії легше підтримувати.
Продовжимо розглядати наш приклад із summa(n). Є дві вимоги, без виконання яких, наш алгоритм не буде працювати:
Має бути чітка умова, виконавши яку процес зупиниться і не буде повторюватися нескінченно. Тобто, така умова дає можливість функції завершити роботу. У програмуванні це і називається базовим випадком. У нашій ситуації, функція викликатиме себе, поки не знайде «коробку з ключем».
При цьому, чим більше функція зробить викликів, тим більшою буде глибина рекурсії.
Для того, щоб базовий випадок взагалі відбувся, потрібна робоча передача змінених даних кожної нової функції. Наприклад перший виклик n=5, другий n=4, і т.д. І лише коли n стає рівним 1, завершиться рекурсія.
Тепер ми звернемо увагу безпосередньо на програмування з Python.
Отже, є «материнська» функція та «дочірня». У той момент, коли функція викликає сама себе, дія «материнської» зупиняється, а натомість починається виконання «дочірньої».
Розглянемо рекурсивну функцію з прикладу summa(5). У комп'ютері зберігаються дані про функції у вигляді блоку, в якому своєю чергою встановлено значення змінної n та код, який виконується. Наочно це виглядає так:
За виконання функції summa(5) починає викликати summa(4). У цей час формується новий блок і розміщується над попереднім:
Так триває доти, доки працює рекурсія функції. При цьому щойно починає працювати новий блок, інші ніяк не уведені в експлуатацію і просто зберігають наявні дані.
І так продовжується до того моменту, коли рекурсія досягає базового випадку:
Далі summa(1) повертає одиницю, завершує роботу та виходить зі стека. У верхній частині залишається summa(2). Тепер summa(2) продовжує виконання з того моменту, на якому зупинилася. За нею - summa (3) і так далі до завершення стека. Під час цього процесу ми можемо зауважити про деяку особливість рекурсії функції у програмуванні. Проблема в тому, що в час, коли рекурсивні функції виконуються, вони зберігають дані про всі незавершені функції, внаслідок цього підвищується споживання пам’яті.
Ось тут важливо згадати особливості мови програмування Python, він має обмеження стека до 1 000 викликів. Тобто, коли чисельність дзвінків перевищує ліміт, ви отримаєте повідомлення про помилку, а саме - “Переповнення стека”. Важливо пам’ятати про це обмеження, коли ви працюєте в середовищі Python взагалі, а зокрема з рекурсією функції.
Прочитавши цю статтю, ви можете задати собі одне важливе запитання: “А чи взагалі потрібно користуватися рекурсією функції в Python, якщо цей результат можна отримати й за допомогою ітеративних алгоритмів?” Питання абсолютно логічне!
Є ситуації, в яких ітеративні цикли будуть ефективнішими. До того ж, вони також можуть використовувати рекурсивні структури даних. Також, рекурсивні функції займають відчутно більше пам’яті, тому що постійно заповнюють новими шарами. Хоча рекурсивні функції мають відчутно вищу ефективність.
Загалом, рекурсивні функції це інструмент, на вивчення та освоєння якого потрібно прикласти деякі сили. При неправильному використанні рекурсія невигідна, адже обчислення проводяться частіше, ніж це справді треба. Щоб уникати подібних помилок, ознайомлюватись з рекурсивними функціями потрібно з найпростіших задач.
Головна перевага рекурсивних функцій над ітеративними, це простота коду.
def factorial_iterative(num):
factorial = 1
if num < 0:
print("Factorial is not calculated for negative numbers")
else:
for i in range (1, num + 1):
factorial = factorial*i
print(f"Factorial {num} is {factorial}")
>>> import sys
>>> sys.getrecursionlimit()
3000
