Информатика · объяснение и практика

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

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Переменные, ветвления, циклы и функции · Учебная карта

Главная мысль

Для завершающейся рекурсии нужны достижимый базовый случай и уменьшение подходящей меры задачи. Наличие строки return само по себе не гарантирует остановку. Область допустимых входов должна совпадать с переходом рекурсивного вызова.

Как задача уменьшается до простого случая

Определим сумму первых n натуральных чисел для целого n ≥ 0. При n = 0 возвращаем 0, иначе возвращаем n плюс результат той же функции для n−1. Для n = 3 цепочка идёт 3→2→1→0. После базового ответа 0 вычисления возвращаются назад:1, затем 3, затем 6.

Мера задачи — неотрицательное целое n. На каждом небазовом шаге оно уменьшается на 1 и потому достигает нуля за конечное число шагов. Это объяснение важнее одного успешного запуска. Проверка только n = 3 не показывает, что произойдёт при других типах и знаках входа. Условие задачи должно быть частью контракта функции.

Какие ошибки не исправляет базовая ветка

Если сохранить базу n = 0, но вызывать функцию с n+1, положительный вход удаляется от остановки. Если вход −1, а переход n−1, цепочка −1, −2, −3 тоже никогда не достигнет нуля. Поэтому отрицательные значения нужно отклонить либо определить другую содержательную задачу и другой переход. Молча принимать любой числовой объект нельзя.

Для дробного n = 0,5 вычитание единицы также не приводит к точному нулю. База и тип меры связаны: доказательство для целых не переносится на вещественные входы. Нельзя заменять условие на удобное n ≤ 0 без проверки смысла: тогда отрицательное значение даст ответ, который может не соответствовать заявленной сумме первых натуральных чисел.

Пример

Рекурсивная функция для целого n ≥ 0 возвращает 1 при n = 0, иначе n·f(n−1). Чему равно f(4)?

Это факториальная рекурсия:4·3·2·1·1 = 24. Базовое 1 нужно для нейтрального элемента умножения; возврат 0 обнулил бы результат.

Почему логическое завершение не снимает ограничений среды

Даже корректная рекурсия для очень большого n может превысить допустимую глубину вызовов Python и завершиться RecursionError. Это ограничение выполнения, а не опровержение математического доказательства конечности. Повышать лимит без оценки ресурсов рискованно; линейную сумму обычно проще посчитать циклом или формулой.

Рекурсия полезна для деревьев и разбиения задачи на подзадачи, но каждый вызов использует ресурсы стека. Проверяют и базу, и размер входа, и максимальную глубину. Если подзадачи повторяются, количество вызовов может расти намного быстрее глубины. Таким образом, завершение, время и память — три разных вопроса. Хорошее объяснение не обещает эффективность только потому, что функция записана коротко и имеет базовый случай.

От чтения к действию

А теперь — вы

Для целого n ≥ 0 база n = 0. Какой переход гарантированно приближает положительный n к базе?

Частые вопросы

Базовый случай гарантирует остановку любого входа?

Нет. Переход должен приводить к нему для всей заявленной области допустимых значений.

RecursionError означает бесконечную математическую задачу?

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

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться