В каких случаях используется рекурсия

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

1. Обход деревьев и графов - например, поиск в глубину (DFS)
2. Разделяй и властвуй - задачи типа сортировки слиянием или быстрой сортировки
3. Математические последовательности - числа Фибоначчи, факториалы
4. Обработка вложенных структур - JSON, XML, HTML

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

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

Важно:

• Всегда должен быть базовый случай (условие выхода)
• Глубина рекурсии ограничена стеком вызовов
• Для некоторых задач итеративное решение может быть эффективнее

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