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

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

Ключевые особенности рекурсии:

• Базовый случай: Условие выхода из рекурсивных вызовов. Без него рекурсия приведет к бесконечному циклу.
• Рекурсивный случай: Условие, при котором функция делает вызов самой себя с измененными аргументами, приближающимися к базовому случаю.

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

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

Недостатки:

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

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

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

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