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

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

Примеры использования:

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

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

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

# Пример использования
result = factorial(5)
# result будет 120

Недостатки рекурсии:

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