Что такое рекурсия в программировании?

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

Принцип работы:

Рекурсивное решение задачи состоит из двух основных частей:

1. Базовый случай (Base Case): Условие, при котором функция прекращает вызывать саму себя и возвращает конкретное значение. Это критически важно для предотвращения бесконечной рекурсии и переполнения стека.
2. Рекурсивный случай (Recursive Case): Функция вызывает саму себя с изменёнными аргументами, которые постепенно приближают её к базовому случаю.

Почему используется?

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

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

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

print(factorial(5)) # Выведет 120

Ограничения и особенности:

• Переполнение стека: Каждый рекурсивный вызов добавляет кадр в стек вызовов. Слишком глубокая рекурсия может привести к переполнению стека (Stack Overflow Error).
• Производительность: Рекурсивные решения могут быть менее эффективными по памяти и времени выполнения, чем итеративные, из-за накладных расходов на управление стеком вызовов.
• Ограничение в Python: В Python по умолчанию существует ограничение на глубину рекурсии (обычно около 1000 вызовов), которое можно изменить, но это не всегда рекомендуется.