Что такое рекурсия: база и шаг

Рекурсия выглядит как фокус: функция вызывает сама себя, и это как-то работает. Никакого фокуса нет — работает стек. Стек — это структура данных, устроенная как стопка тарелок: положить и снять можно только сверху. По-английски принцип называют LIFO — последним пришёл, первым ушёл. Каждый раз, когда программа вызывает функцию, она кладёт на стек кадр вызова: значения аргументов, локальные переменные и адрес, куда вернуться после завершения. Пока функция не закончила работу, её кадр лежит на стеке и занимает память. Посмотрим на F(4) при правиле F(n) = n · F(n−1), F(1) = 1: Кладём на стек F(4) → она не может ответить, пока не узнает F(3), поэтому кладём F(3) → та ждёт F(2) → та ждёт F(1). На стеке одновременно четыре кадра. F(1) — база, она отвечает сразу: 1. Её кадр снимается со стека, значение возвращается в F(2). Теперь F(2) может досчитать: 2 · 1 = 2. Её кадр снимается, значение уходит в F(3): 3 · 2 = 6. Затем F(4): 4 · 6 = 24. Из этого устройства следуют два практических вывода. Вывод 1. Без базы программа падает. Если условия остановки нет или шаг не уменьшает аргумент, кадры кладутся на стек бесконечно, память кончается, и Python сообщает об ошибке RecursionError: maximum recursion depth exceeded. По умолчанию предел глубины в Python около тысячи вызовов. Вывод 2. Глубина рекурсии — это расход памяти. Для F(100000) рекурсивное решение не годится, а цикл справится, потому что он не хранит сто тысяч кадров. Исторически именно стек сделал рекурсию возможной в языках программирования: механизм хранения кадров на стеке был реализован при создании компилятора Алгола-60 в начале 1960-х годов, и с тех пор так работают почти все языки.

Отсюда и практическое правило отладки: если программа падает с RecursionError, проверять надо не соотношение, а достижимость базы. Чаще всего аргумент меняется не в ту сторону (F(n + 1) вместо F(n - 1)) или база задана для n = 1, а рекурсия проскакивает её и уходит в ноль и дальше. Печать аргумента в первой строке функции показывает это за один запуск.

В задании 16 встречаются два разных типа рекурсивных алгоритмов, и путать их нельзя. Тип 1: функция, которая возвращает число. Задано соотношение вида «F(n) = 0, если n ≤ 1; F(n) = F(n−1) + n², если n > 1», и спрашивают значение F(28). Здесь нужно посчитать одно число, и удобнее всего идти снизу вверх, заполняя таблицу от базы. Тип 2: процедура, которая ничего не возвращает, но печатает. Например: ```

F(n - 1) print(n) F(n - 2) ``` И спрашивают: что напечатает F(5), или сколько всего символов будет выведено, или какая цифра окажется на третьем месте. Здесь таблица не поможет — важен порядок выполнения. Решают такие задачи двумя способами. Способ А: раскрутить вручную по правилу «сверху вниз, слева направо». Команды внутри функции выполняются по очереди, и вложенный вызов выполняется полностью, прежде чем управление вернётся к следующей строке. Способ Б: просто запустить программу. На экзамене разрешён компьютер с интерпретатором, и переписать пять строк быстрее и надёжнее, чем раскручивать дерево на бумаге. Важная деталь порядка. В примере выше вызов F(n−1) стоит до печати, значит, сначала напечатаются все меньшие значения, а n — позже. Если переставить строки местами, вывод изменится полностью. Именно на этом и строят задания: два варианта отличаются только положением строки print.

Ошибка 1. Неверно прочитана база. «F(n) = 0, если n ≤ 1» означает, что нулём равны и F(1), и F(0), и F(−5). А запись «F(1) = 2; F(2) = 3» задаёт две базы, и таблицу надо начинать с третьего значения. Ошибка 2. Путают n и F(n). В соотношении F(n) = F(n−1) + n² второе слагаемое — это квадрат самого n, а не квадрат предыдущего значения функции. Ошибка 3. Считают рекурсивно без мемоизации. Для F(n) = F(n−1) + F(n−2) наивная рекурсия при n = 40 делает свыше трёхсот миллионов вызовов. Программа либо считает минутами, либо падает. Ошибка 4. Забывают про предел глубины. Если решение всё-таки рекурсивное и n велико, нужно import sys; sys.setrecursionlimit(10000), иначе Python остановится на глубине около тысячи. Ошибка 5. В задачах с печатью отвечают набором чисел вместо последовательности. Спрашивают обычно именно порядок вывода, и переставленные цифры — уже неверный ответ. Ошибка 6. Отвечают значением функции, когда спрашивают сумму цифр. Формулировку «в ответе укажите сумму цифр числа F(20)» пропускают глазами и пишут само число.

И напоследок про стек вызовов. Каждый незавершённый вызов хранит свои локальные переменные и точку возврата, поэтому глубокая рекурсия расходует память пропорционально глубине. Для задач ЕГЭ этого хватает с запасом, но понимать механизм стоит: именно стек объясняет, почему печать после рекурсивного вызова выводит числа в обратном порядке и почему при бесконечной рекурсии программа падает не сразу, а исчерпав отведённое ей место.

Почти всё, что делает рекурсия, умеет и обычный цикл. Выбор между ними — не вопрос вкуса, и на экзамене он решается быстро.

Рекурсия удобнее, когда задача естественно сводится к себе же меньшего размера и когда таких сведений несколько. Рекуррентное соотношение F(n) = F(n−1) + F(n−2) переносится в рекурсию дословно, а в цикл — только после размышлений о том, какие значения хранить. Задачи с обходом дерева, подсчётом путей, разбором вариантов пишутся рекурсией в три строки.

Цикл удобнее, когда шаг простой и линейный: пройти по списку, накопить сумму, найти максимум. Рекурсия здесь ничего не даёт, зато тратит стек.

Три практических соображения.

Глубина. Каждый рекурсивный вызов занимает место в стеке, и Python по умолчанию разрешает около тысячи вложенных вызовов. Для F(50) это не проблема, для F(5000) — уже да, и нужна строка sys.setrecursionlimit(100000). Цикл глубины не имеет вовсе.

Скорость. Вызов функции дороже витка цикла в несколько раз. На задачах ЕГЭ это незаметно, но если рекурсия работает подозрительно долго, первым делом проверьте не скорость, а наличие кэша: почти всегда дело в том, что одно значение считается тысячи раз.

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

Практический вывод для ЕГЭ: линии 13 и 16 пишите рекурсией с @lru_cache, линии 17, 24, 25 и 26 — циклом. Это не догма, но так короче и надёжнее в подавляющем большинстве вариантов.

Иногда рекурсию просят заменить циклом — или это делают сами, чтобы обойти ограничение на глубину. Перевод механический, и знать его полезно.

Линейная рекурсия (один вызов, аргумент меняется на единицу) превращается в обычный цикл с накопителем. Факториал F(n) = n · F(n−1) становится:

rezultat = 1

for i in range(2, n + 1):

rezultat *= i

Рекурсия с несколькими предыдущими значениями превращается в цикл со скользящим окном из переменных: сколько значений в соотношении, столько переменных и нужно.

Рекурсия с произвольными переходами (вызовы вида F(n // 2) или F(n − 7)) в простой цикл не переписывается — там нужна полная таблица, заполняемая в правильном порядке. Именно поэтому в линиях 13 и 16 удобнее оставить рекурсию с кэшем: порядок заполнения она выбирает сама.

Рекурсия с двумя ветвями и деревом вариантов (подсчёт путей, обход графа) переписывается через явный стек или очередь: то, что рекурсия хранила в стеке вызовов, программа хранит в списке. Кода становится больше, зато глубина перестаёт быть ограничением.

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

Одно предупреждение напоследок. Переписывая рекурсию циклом, легко потерять порядок вычислений: цикл идёт по возрастанию индекса, а соотношение может требовать значений, которых на этом шаге ещё нет. Проверяется это просто — выпишите, от каких индексов зависит F[i], и убедитесь, что все они меньше i. Если есть зависимость от большего индекса, простым циклом не обойтись, и надо либо менять направление обхода, либо возвращаться к рекурсии с кэшем.