Что такое рекурсия и в каких задачах ее применяют

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

Любая рекурсивная функция состоит из двух частей:

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

Преимущества:

• Элегантность и читаемость: Код для древовидных структур (файловые системы, DOM) или математических задач (факториал, числа Фибоначчи) становится значительно проще и понятнее.
• Естественное решение: Для задач, которые по своей природе рекурсивны (например, алгоритм "разделяй и властвуй"), рекурсия является наиболее естественным подходом.

Недостатки:

• Риск переполнения стека: Глубокая рекурсия может исчерпать стек вызовов и привести к ошибке StackOverflowError.
• Производительность: Рекурсивные вызовы обычно медленнее и требуют больше памяти, чем итеративные решения из-за накладных расходов на вызов функций.

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

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

print(factorial(5)) # Вывод: 120

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