Рекурсивна функція у Python

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

Розглянемо простий приклад рекурсивної функції для обчислення факторіалу:

def factorial(number):
    if number == 1:
        return 1
    return number * factorial(number - 1)


result = factorial(5)
print(result)  # 120

Як виглядає рішення цієї задачі за допомогою циклу for:

def factorial(number):
    x = 1
    for i in range(1, number + 1):
        x *= i
    return x


result = factorial(5)
print(result)  # 120

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

Стек викликів

Стек – це структура даних типу LIFO (Last In, First Out), де останній доданий елемент витягується першим.

Стек викликів – це спеціальна область пам’яті, яка використовується для зберігання інформації про активні виклики функцій під час виконання програми.

Коли викликається функція, у стеку створюється спеціальний кадр (stack frame), який містить:

  • адресу, за якою потрібно продовжити виконання програми після завершення функції
  • значення аргументів, переданих функції
  • локальні змінні функції
  • іншу службову інформацію, пов’язану з контекстом виконання

Кожен stack frame розміщується у стеку викликів, створюючи ланцюжок активних функцій.

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

Розробнику не потрібно вручну керувати стеком викликів – створення фреймів, їх розміщення та видалення, автоматично виконує інтерпретатор Python.

Базовий випадок та рекурсивний випадок

Рекурсивна функція складається з двох частин: базового випадку та рекурсивного випадку:

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

Під час написання рекурсивної функції, обов’язково потрібно вказати умову, за якої рекурсія має перерватися – це і є базовий випадок. Рекурсивний випадок відповідає за рекурсію і поступове приведення до базового випадку.

Повернемося до прикладу з обчисленням факторіалу:

def factorial(number):
    if number == 1:
        return 1
    return number * factorial(number - 1)

Тут за базовий випадок відповідає фрагмент коду:

if number == 1
    return 1

За рекурсивний випадок:

return number * factorial(number - 1)

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

Приклад використання рекурсивної функції Python

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

import os


def get_directory_size(path):
    total_size = 0
    try:
        for item in os.listdir(path):
            full_path = os.path.join(path, item)
            if os.path.isfile(full_path):
                total_size += os.path.getsize(full_path)
            elif os.path.isdir(full_path):
                total_size += get_directory_size(full_path)
    except OSError as e:
        print(f'Permission error accessing \'{path}\': {e}')
        return 0
    return total_size


# Example usage:
directory_path = '/path/to/your/directory'  # Replace with the actual path
size_in_bytes = get_directory_size(directory_path)

if size_in_bytes > 0:
    size_in_megabytes = size_in_bytes / (1024 * 1024)
    print(f'Total size of directory \'{directory_path}\' is: {size_in_megabytes:.2f} MB')
else:
    print(f'Failed to get the size of directory \'{directory_path}\'.')

У цьому прикладі:

  • Базовий випадок: якщо поточний елемент циклу є файлом – os.path.isfile(full_path), ми отримуємо його розмір за допомогою os.path.getsize() та додаємо до total_size.
  • Рекурсивний випадок: якщо елемент є директорією – os.path.isdir(full_path), ми знову викликаємо нашу функцію get_directory_size() з повним шляхом до цієї підпапки (тобто відбувається рекурсивний виклик). Функція починає обробляти вміст вже цієї вкладеної папки, включаючи її файли та папки.
  • Агрегація результатів: кожен рекурсивний виклик повертає розмір обробленої папки, і ці значення поступово додаються у змінну total_size.

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

Швидкість виконання рекурсії та ітерації

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

Для порівняння скористаємося задачею по обчисленню послідовності Фібоначчі:

import time


def fibonacci_recursive(n):
    if n <= 1:
        return n
    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


number = 35

start = time.perf_counter()
recursive = fibonacci_recursive(number)
recursive_time = (time.perf_counter() - start) * 1000  # у мілісекундах

start = time.perf_counter()
iterative = fibonacci_iterative(number)
iterative_time = (time.perf_counter() - start) * 1000  # у мілісекундах

print(f'Recursive result: {recursive}, time: {recursive_time:.8f} ms')
print(f'Iterative result: {iterative}, time: {iterative_time:.8f} ms')

Результати виконання:

Recursive result: 9227465, time: 2012.61199999 ms
Iterative result: 9227465, time: 0.00599999 ms

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

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1)
│   │   │   └── fibonacci(0)
│   │   └── fibonacci(1)
│   └── fibonacci(2)
│       ├── fibonacci(1)
│       └── fibonacci(0)
└── fibonacci(3)
    ├── fibonacci(2)
    │   ├── fibonacci(1)
    │   └── fibonacci(0)
    └── fibonacci(1)

Кількість рекурсивних викликів зростає зі збільшенням n, що призводить до значного збільшення часу виконання, особливо для великих значень n.

Оптимізація рекурсії

Якщо застосування рекурсії для розв’язання задачі неминуче, є простий спосіб прискорити виконання рекурсивної функції – мемоізація (зберігання проміжних результатів для запобігання повторних обчислень). Для цього можна скористатись декоратором @lru_cache з вбудованого модуля Python functools:

import time
from functools import lru_cache


def fibonacci_plain(n):
    if n <= 1:
        return n
    return fibonacci_plain(n - 1) + fibonacci_plain(n - 2)


@lru_cache(maxsize=None)
def fibonacci_cached(n):
    if n <= 1:
        return n
    return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)


number = 35

start = time.perf_counter()
plain = fibonacci_plain(number)
plain_time = (time.perf_counter() - start) * 1000  # у мілісекундах

start = time.perf_counter()
cached = fibonacci_cached(number)
cached_time = (time.perf_counter() - start) * 1000  # у мілісекундах

print(f'Without cache result: {plain}, time: {plain_time:.8f} ms')
print(f'With cache result: {cached}, time: {cached_time:.8f} ms')

Результат виконання:

Without cache result: 9227465, time: 1966.18579997 ms
With cache result: 9227465, time: 0.04530000 ms

Декоратор @lru_cache дозволяє Python запам’ятовувати результати викликів функції. Якщо функція викликається з тими самими аргументами повторно, обчислення не виконуються ще раз – Python просто повертає збережений результат з пам’яті (кешу).

Мітки: