Рекурсія у

Про концепцію Рекурсія

Рекурсія дає змогу багаторазово виконувати код усередині функції завдяки тому, що функція викликає саму себе. Функції, які викликають самі себе, називають рекурсивними. На рекурсію можна дивитися як на ще один спосіб організувати цикл або ітерацію. І так само, як у циклі, щоб визначити, коли зупинити рекурсивне виконання, використовують булевий вираз (англ. Boolean) або перевірку на True/False.

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

Реалізація через цикл і через рекурсію

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

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

Рекурсія: чому так і чому ні?

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

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

Стратегія циклу чи рекурсії: тривога Індіри

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

Адя, яка лише вчиться програмувати на Python, пише програму, спираючись на свої перші міркування. Вона хоче повертати list із датами зарахувань, щоб їх можна було надрукувати. Вона хоче написати функцію, яка працюватиме для будь-якого року. Якщо графік зміниться (або якщо інші родичі попросять Адю обчислити їхні графіки зарахувань), вона вирішує, що функція має приймати додатковий параметр для дня тижня. Зрештою Адя вирішує, що функції потрібен параметр для якого саме дня тижня в місяці: першого, другого тощо. З огляду на всі ці вимоги вона вирішує скористатися класом date, імпортованим із datetime. Зібравши все це докупи, Адя отримує:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

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

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

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

Адя рада, що більше немає вкладених циклів, немає змінюваного стану і на 2 рядки коду менше!

Її трохи непокоїть, що рекурсивний підхід робить більше кроків, ніж циклічний, а отже, він менш «продуктивний». Але переписування задачі через рекурсію точно допомогло їй упоратися з потворними вкладеними циклами (загрозою для продуктивності), масштабною зміною стану й плутаниною в складній умовній логіці. Код також здається їй більш «читабельним». Вона впевнена, що коли повернеться до нього після перерви, то зможе легко його прочитати й згадати, що він робить.

У майбутньому Адя, можливо, спробує спершу розвʼязувати задачі рекурсивно. Їй може бути легше спочатку пройти задачу чіткими кроками, коли вкладеність, зміна стану й складність зведені до мінімуму. Коли основну логіку буде зʼясовано, вона зможе зосередитися на тому, щоб оптимізувати початкові рекурсивні кроки в продуктивніший циклічний підхід.

Ще пізніше, коли вона дізнається про tuples, Адя могла б розглянути подальші «оптимізації», як-от list comprehension разом із Calendar.itermonthdates або мемоізацію певних значень.

Різновид рекурсії: хвостовий виклик

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

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Це надрукує:

The step is 1
The step is 2
retval is 3 after recursion

Щоб переробити його на хвостовий виклик, зробіть retval параметром print_increment.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

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

Обмеження рекурсії в Python

Деякі мови вміють оптимізувати хвостові виклики так, що кожен рекурсивний виклик повторно використовує кадр стека першого виклику функції (подібно до того, як цикл повторно використовує кадр), а не додає до стека ще один кадр. Python не належить до таких мов. Щоб захиститися від переповнення стека, Python має обмеження рекурсії, яке типово дорівнює тисячі кадрів. Виняток RecursionError виникає, коли інтерпретатор виявляє, що обмеження рекурсії перевищено. Можна скористатися методом sys.setrecursionlimit, щоб збільшити обмеження рекурсії, але це ризикує спричинити помилку сегментації під час виконання, яка обвалить програму, а можливо, й операційну систему.

Ресурси

Щоб дізнатися більше про використання рекурсії в Python, можна почати з

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively