Рекурсія – тема в математиці та комп'ютерних науках. У мовах програмування, термін рекурсія відповідає функції, яка викликає себе. Інакше кажучи, це оголошення функції, що включає в себе тіло функції та її виклик. Одним із перших попереджень, яке я отримав, коли мій викладач програмування розповідав про рекурсію, було те, що можна випадково створити нескінченний цикл, який спричинить зависання програми. Це може статися, тому що в результаті використання рекурсії, функція може безкінечно викликати себе. Тому, як і з іншими потенційно нескінченними циклами, потрібно переконатись, що існує умова виходу з циклу. У більшості рекурсивних функцій, ідея полягає в тому, щоб розбити процедуру на менші фрагменти, які можна опрацьовувати тією ж функцією.
Найпопулярніший спосіб опису рекурсії зазвичай ілюструється шляхом створення функції обчислення факторіалу. Факторіал виглядає приблизно так: 5! Зауважте, що після числа є знак оклику. Така нотація вказує на те, що його потрібно розглядати як факторіал. Це означає, що 5! = 54321 або 120.
Погляньмо на простий приклад:
def factorial(number):
if number == 0:
return 1
else:
return number * factorial(number-1)
if __name__ == '__main__':
print(factorial(3))
print(factorial(5))
У цьому коді ми перевіряємо чи переданий параметр дорівнює нулю. Якщо так, повертаємо одиницю. Інакше, ми множимо це число на результат виконання цієї ж функції але з параметром: число мінус один. Можна трохи модифікувати цей код, щоб отримати кількість разів, яку виконалась рекурсія:
def factorial(number, recursed=0):
if number == 0:
return 1
else:
print('Recursed {} time(s)'.format(recursed))
recursed += 1
return number * factorial(number-1, recursed)
if __name__ == '__main__':
print(factorial(3))
Щоразу, коли викликаємо функцію factorial та число більше від нуля, виводимо кількість рекурсивних викликів. Останнім рядком, який ви бачите, повинен бути «Recursed 2 time(s)», тому що для обчислення факторіалу 3 функцію factorial потрібно викликати двічі.
Ліміт рекурсії в Python
На початку цієї статті я згадував, що можна створити нескінченний рекурсивний цикл. Це можливо в деяких мовах програмування, але в Python є ліміт рекурсії. Це можна перевірити, виконавши наступне:
>>> import sys
>>> sys.getrecursionlimit()
1000
Якщо Ви вважаєте, що ліміт є занадто малим для Вашої програми, його можна встановити за допомогою функції setrecursionlimit() модуля sys. Спробуймо створити рекурсивну функцію, яка перевищить ліміт, щоб побачити, що відбудеться:
def recursive():
recursive()
if __name__ == '__main__':
recursive()
Якщо Ви запустите цей код, то повинні побачити такий виняток: RuntimeError: maximum recursion depth exceeded. Python запобігає створенню функції, яка вилиється у нескінченний рекурсивний цикл.
Декомпозиція списків за допомогою рекурсії
Тим не менше, є й інші речі, які можна робити за допомогою рекурсії, окрім обчислення факторіалів. Більш практичною ілюстрацією було б, наприклад, створення функції для розкладання вкладеного списку на складові:
# flatten.py
def flatten(a_list, flat_list=None):
if flat_list is None:
flat_list = []
for item in a_list:
if isinstance(item, list):
flatten(item, flat_list)
else:
flat_list.append(item)
return flat_list
if __name__ == '__main__':
nested = [1, 2, 3, [4, 5], 6]
x = flatten(nested)
print(x)
У результаті виконання цього коду, повинен бути список цілих чисел, а не список цілих чисел і ще один список. Звичайно, є й багато інших ефективних шляхів розкласти вкладений список на складові, такий як використання itertools.chain(). Можливо Ви захочете поглянути на код класу chain(), так як у ньому застосовується зовсім інший підхід для декомпозиції списку.
Ще немає коментарів