Что такое рекурсия

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

Основные условия:

1. Базовый случай (когда рекурсия останавливается)
2. Рекурсивный шаг (вызов функции с изменёнными параметрами)

Пример (факториал на Python):

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

Опасности:

• Переполнение стека при глубокой рекурсии
• Неоптимальное использование памяти
• Возможна бесконечная рекурсия без базового случая

Для сложных задач часто лучше использовать итеративные решения.