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

Принцип работы:

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

Пример: вычисление факториала числа n (n!)

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

Здесь factorial вызывает себя с n-1, пока не дойдёт до 0, после чего начинает возвращать значения вверх по цепочке.

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

Объясните концепцию рекурсивных функций и как они работают