Как создавать и использовать рекурсивные функции в Python

• 25.06.2023
• 245
• Основы Python
• Функции

Python, как и многие другие языки программирования, поддерживает рекурсивные функции, или функции, которые могут вызывать сами себя. Рекурсия — это мощный инструмент, который может быть использован для решения сложных задач, которые могут быть разбиты на более маленькие, повторяющиеся подзадачи.

Основы рекурсии

Рекурсия в программировании — это концепция, при которой функция вызывает саму себя напрямую или косвенно. Важными элементами рекурсивной функции являются базовый случай (условие, при котором рекурсия останавливается) и рекурсивный случай (часть функции, где происходит рекурсивный вызов).

Вот простой пример рекурсивной функции, которая вычисляет факториал числа:

def factorial(n):
    if n == 0:  # Базовый случай
        return 1
    else:  # Рекурсивный случай
        return n * factorial(n-1)

print(factorial(5))

#120

Разбиение задачи на подзадачи

Один из ключевых моментов в рекурсии заключается в разбиении основной задачи на более мелкие подзадачи. Возьмем, к примеру, задачу вычисления факториала числа. Факториал числа n (обозначается n!) — это произведение всех целых чисел от 1 до n. Эту задачу можно разбить на подзадачи — вычисление факториала числа n-1, n-2 и так далее, до 1.

# Факториал числа 5:
# 5! = 5 * 4 * 3 * 2 * 1 = 5 * (4!)
# То есть, факториал числа 5 - это произведение числа 5 на факториал числа 4.

Это разбиение задачи на подзадачи прямо отражено в вышеупомянутой функции factorial().

Рекурсия против итерации

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

Вернемся к примеру с вычислением факториала. Вот как можно переписать функцию factorial() с использованием цикла:

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial(5))

#120

Однако, есть важные моменты, которые следует учесть при выборе между рекурсией и итерацией:

• Рекурсивные функции могут быть более читаемыми и легче понимаемыми, особенно при решении сложных задач.
• Рекурсивные функции, особенно те, которые вызывают себя множество раз, могут быстро исчерпать стек вызовов Python, что приводит к ошибке переполнения стека.
• Итеративные решения обычно более эффективные по производительности, поскольку они не включают в себя дополнительные затраты на многократные вызовы функций.

Пример использования рекурсии

Рекурсия может быть использована для решения множества задач. Рассмотрим самый наглядный.

Решение задачи о Ханойской башне

Ханойская башня — это классическая математическая игра или головоломка. Имеется три стержня, и на один из них нанизаны кольца, самое большое из которых лежит внизу, а самое маленькое — наверху. Задача заключается в том, чтобы переместить пирамиду из n колец с одного стержня на другой, следуя следующим правилам:

• За один ход можно перемещать только одно кольцо.
• Можно брать только верхнее кольцо с одного из стержней и перекладывать его на верхушку любого из трёх стержней.
• Кольцо нельзя класть на кольцо меньшего размера.

def hanoi(n, source, target, auxiliary):
    if n > 0:
        # перемещаем n - 1 дисков на вспомогательный стержень
        hanoi(n - 1, source, auxiliary, target)

        # перемещаем диск на целевой стержень
        print('Move disk from rod {} to rod {}'.format(source, target))

        # перемещаем n - 1 дисков на целевой стержень
        hanoi(n - 1, auxiliary, target, source)

hanoi(3, 'A', 'C', 'B')

#Move disk from rod A to rod C
#Move disk from rod A to rod B
#Move disk from rod C to rod B
#Move disk from rod A to rod C
#Move disk from rod B to rod A
#Move disk from rod B to rod C
#Move disk from rod A to rod C

Рекурсия и стек вызовов

При работе с рекурсией важно понимать, как Python использует стек вызовов для отслеживания функций и их возвращаемых значений. Каждый раз, когда функция вызывается, информация о вызове (включая аргументы функции и местоположение, куда функция должна вернуться после завершения) добавляется в стек вызовов. Когда функция заканчивает выполнение, информация о вызове удаляется из стека, и выполнение продолжается с того места, куда указывает вершина стека.

Проблема состоит в том, что размер стека вызовов в Python ограничен. Если рекурсивная функция вызывает себя слишком много раз (то есть глубина рекурсии слишком велика), стек вызовов может быть исчерпан, что приведет к ошибке переполнения стека.

def recursive_function(n):
    if n == 0:
        return 0
    else:
        return 1 + recursive_function(n - 1)

recursive_function(10000)  # вызывает ошибку переполнения стека

Заключение

Рекурсия — это мощный инструмент в программировании, который может быть использован для решения сложных задач, особенно тех, которые могут быть разбиты на подзадачи. Однако при использовании рекурсии важно учитывать ограничения, связанные с размером стека вызовов Python, а также то, что рекурсивные решения могут быть менее эффективными по производительности по сравнению с итеративными.