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

Матрёшка внутри матрёшки

Откройте матрёшку — внутри матрёшка поменьше, внутри неё ещё меньше, и так до самой крошечной, которую уже не открыть. РекурсияПриём, при котором функция вызывает саму себя. Нужен базовый случай, чтобы вызовы завершились. устроена так же: функцияИменованный блок кода, который можно вызывать многократно. Может принимать аргументы и возвращать результат. решает задачу, вызывая саму себя для задачи поменьше, и так до самого простого случая, который решается сразу.

У любой рекурсии есть две обязательные части:

• Базовый случай — самая маленькая матрёшка, которая не открывается. Здесь рекурсия останавливается.
• Шаг рекурсии — вызов самой себя для задачи поменьше, приближающий к базовому случаю.

Проследим вызовы: countdown(3) печатает 3 и зовёт countdown(2), тот печатает 2 и зовёт countdown(1), далее countdown(0) — это базовый случай, он печатает «Пуск!» и возвращается, не вызывая себя. Стопка вызовов «схлопывается» обратно.

Факториал — классика рекурсии

Факториал числа n (записывается n!) — это произведение всех чисел от 1 до n. Например, 4! = 4·3·2·1 = 24. Рекурсивное определение элегантно: n! = n · (n−1)!, а 0! = 1 (это базовый случай).

Как разворачивается factorial(4): оно ждёт factorial(3), тот ждёт factorial(2), и так до factorial(0), которое возвращает 1. Затем результаты перемножаются на обратном пути: 1 → 1·1 → 2·1 → 3·2 → 4·6 = 24.

Вернётся 6: это 3 + 2 + 1 + 0. Функция считает сумму чисел от 1 до n рекурсивно — каждый вызов добавляет своё n к сумме оставшихся.

⚠️ Частые ошибки новичков

Ошибка. Забыть базовый случай. Без него функция вызывает себя бесконечно. Запустите код ниже — увидите RecursionError: maximum recursion depth exceeded. Почините: добавьте в начало if n == 0: return 0.