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

Рекурсия в программировании - это техника, при которой функция вызывает саму себя в процессе своего выполнения. Функция, которая вызывает саму себя, называется рекурсивной функцией, а процесс, в котором функция вызывает саму себя, называется рекурсией.

Основные черты рекурсивных функций:

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

2. Шаг рекурсии: Рекурсивная функция должна двигаться в направлении базового случая. Каждый новый вызов должен приближать нас к завершению рекурсии.

Пример простой рекурсивной функции - вычисление факториала:

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

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

В этом примере, если n равно 0 или 1, функция возвращает 1 (базовый случай). В противном случае, она вызывает саму себя с аргументом n - 1, двигаясь к базовому случаю. Рекурсия завершается, когда достигнут базовый случай.