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

Представьте себе ситуацию, как будто вы смотрите в два зеркала, обращённые друг к другу. Вы видите отражение в отражении, которое продолжается бесконечно… пока, в конце концов, не исчезает. В рекурсии это "исчезновение" очень важно — мы называем его базовым случаем, и именно он останавливает повторение.

Как работает рекурсия

Рекурсивная функция:

1. Проверяет, нужно ли остановиться — это базовый случай.
2. Если нет, вызывает себя с меньшей или более простой версией исходной задачи.

Постоянно разбивая задачу на более мелкие части, рекурсия достигает самой простой версии задачи, решает её, а затем восстанавливает ответ при возврате из всех вызовов.

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

Рассмотрим факториал числа.
В математике факториал n (обозначается как n!) это:

n! = n × (n-1) × (n-2) × ... × 1

Например:

5! = 5 × 4 × 3 × 2 × 1 = 120

Вот рекурсивная версия на Python:

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

print(factorial(5))  # 120

Что здесь происходит:

• Если n равно 0, мы достигли базового случая — по определению 0! равно 1.
• В противном случае умножаем n на factorial(n - 1) (более простая версия той же задачи).
• Это повторяется, пока мы не дойдём до базового случая.

Зачем использовать рекурсию?

Рекурсия может быть:

• Элегантной и краткой для задач с естественно повторяющейся структурой.
• Идеальной для математических задач (факториалы, числа Фибоначчи).
• Необходимой для обхода древовидных данных (файловые системы, генеалогические деревья, поиск в AI игр).

Иногда рекурсия может заменить циклы, хотя не всегда она самый эффективный вариант.

СОВЕТ: Рекурсию проще понять, если думать так: "разбей задачу на более мелкие её же версии, пока не сможешь решить её напрямую."

Распространённые ошибки

ВАЖНО! Всегда определяйте базовый случай — без него функция будет вызывать себя бесконечно, пока Python не выдаст ошибку RecursionError.

Советы для устранения проблем:

• “RecursionError: maximum recursion depth exceeded” → Вы не достигли базового случая или базовый случай задан неверно.
• Если рекурсия кажется слишком сложной для задачи, попробуйте вместо неё использовать цикл.

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