О задании
Скоро мы начнём разбирать алгоритм решения 16 задания ЕГЭ по информатике. Это задание проверяет ваше умение работать с рекурсивными алгоритмами — вам дают функцию, заданную через саму себя, и просят вычислить её значение. Звучит странно? Сейчас разберёмся, что это вообще такое и как с этим работать.
Но, прежде чем переходить к решению конкретных задач, нужно понять, как Python воспринимает рекурсию, почему иногда программа падает с ошибкой и что с этим делать. Именно об этом и поговорим в данной статье.
Что такое рекурсия
Представьте, что вы директор школы и вам нужно подсчитать всех учеников. У вас есть список классов, в каждом классе — список учеников. Просто, правда? И как современный эффективный директор, знающий язык программирования Python, вы можете использовать два вложенных цикла:
Это работает! Но что, если структура усложняется? Что если в школе есть параллели, в параллелях — классы, в классах — группы, а в группах — ученики? Количество вложенных циклов будет расти, код станет громоздким и непонятным.
А теперь другой пример — обход папок на компьютере:
Документы/
│── Учёба/
│ │── Математика/
│ │ └── задачи.txt
│ └── Информатика/
│ └── лекции.pptx
└── Фото/
│── Лето 2012/
│ └── яхта/
│ └── парус.jpg
└── Осень 2007/
│ └── сентябрь/
│ └── горит.gif
Сколько здесь уровней вложенности? А если в папке «Фото» окажется ещё десять папок? Мы просто не можем заранее знать, сколько уровней нужно обойти. Писать циклы для каждого уровня бессмысленно.
Отсюда вырисовывается проблема: мы имеем задачи с неизвестной глубиной вложенности. Для решения таких задач применяют рекурсивные методы.
Рекурсия – это процесс, при котором функция (или алгоритм) вызывает саму себя. В программировании это означает, что такая функция решает большую задачу, разбивая её на более мелкие подзадачи того же типа.
Давайте разберём классический пример рекурсивных задач: вычисление факториала числа.
Как вы посчитаете факториал пятёрки?
5! = 5 × 4 × 3 × 2 × 1 = 120
Но можно заметить интересную вещь:
5! = 5 × (4 × 3 × 2 × 1)
А ведь (4 × 3 × 2 × 1) — это просто 4! (4 факториал).
Получается, для вычисления факториала 5 нужно умножить 5 на факториал 4. Продолжим эту логику:
- Факториал 5 = 5 × факториал 4
- Факториал 4 = 4 × факториал 3
- Факториал 3 = 3 × факториал 2
- Факториал 2 = 2 × факториал 1
- Факториал 1 = 1 (наша остановка)
Мы разбили сложную задачу на более мелкие подзадачи того же типа. Это и есть рекурсия.
Обратите внимание на два важных момента:
- Рекурсивный случай: n × (n-1)! — формула, которая использует саму себя
- Базовый случай: 1! = 1 — условие остановки
Без базового случая функция будет вызывать себя бесконечно, и программа зависнет.
Рекурсия в Python
Теперь напишем рекурсивную функцию для вычисления факториала:
Давайте разберём, что происходит при вызове factorial(5):
- Функция проверяет: n == 1? Нет, n = 5
- Возвращает 5 × factorial(4)
- Чтобы вычислить factorial(4), функция вызывает саму себя с аргументом 4
- Процесс повторяется до factorial(1)
- factorial(1) возвращает 1 (базовый случай!)
- Начинается «обратный путь»: все отложенные вычисления выполняются
Выглядит это так:
Рекурсия особенно полезна для задач, где:
- Структура данных содержит саму себя: обход папок на компьютере (папка содержит папки), работа с деревьями (узел содержит узлы), обход HTML DOM-дерева
- Задачу можно разбить на одинаковые подзадачи: вычисление факториала, числа Фибоначчи, сортировка (быстрая сортировка, сортировка слиянием)
- Нужно перебрать все возможные варианты: решение судоку, поиск пути в лабиринте, расстановка ферзей на шахматной доске
Работа рекурсии
Итеративный подход
Прежде чем углубиться в рекурсивные функции, давайте разберёмся: зачем вообще нужна рекурсия, если можно использовать обычные циклы?
Любую рекурсивную функцию можно переписать через циклы, и наоборот. Но иногда рекурсия делает код намного проще.
Вот тот же факториал через цикл:
Далее давайте разберем несколько примеров решения стандартных задач обоими методами: итеративным и рекурсивным. И выясним, когда же лучше использовать рекурсию, а когда итеративное вычисление.
Задача: найти сумму всех чисел от 1 до n.
Итеративный подход:
Рекурсивный:
Задача: найти сумму всех элементов в списке.
Итеративный:
Рекурсивный:
Задача: развернуть строку задом наперёд.
Итеративный подход:
Рекурсивный:
Уже можно сделать некоторые выводы. Используйте рекурсию, когда:
- Задача естественным образом разбивается на подзадачи того же типа
- Работаете с древовидными структурами (деревья, файловая система)
- Решаете задачи типа «разделяй и властвуй»
- Код с рекурсией получается значительно проще и понятнее
Примеры: обход дерева, быстрая сортировка, поиск в глубину, backtracking
Используйте циклы, когда:
- Важна производительность и эффективность использования памяти
- Задача естественным образом описывается последовательностью шагов
- Глубина рекурсии может быть очень большой
Примеры: обработка массивов, вычисления с накоплением, простые итерации
Обработка рекурсии: стек вызовов
Когда вы вызываете рекурсивную функцию, Python должен где-то хранить информацию о каждом вызове: значения аргументов, локальные переменные, место в коде, куда нужно вернуться. Всё это называется контекстом выполнения функции.
Где Python хранит эту информацию? В специальной структуре данных под названием стек вызовов.
Стек — это как стопка тарелок. Вы можете положить тарелку наверх или снять верхнюю тарелку. Но вы не можете вытащить тарелку из середины стопки — только сверху. В стеке есть две основные операции:
- Push (поместить) — добавить элемент на верх стека
- Pop (извлечь) — снять элемент с верха стека
Это называется принцип LIFO (Last In — First Out): последним зашёл — первым вышел.
Допустим, у нас есть три функции:
Графически эти вызовы можно представить следующим образом:
Вызов каждой функции помещается в стек. Это как некий список, в который последовательно попадают вызовы функций: снизу первый вызов, сверху – последний.
То есть мы помещаем в него вызовы, как в обычную банку: сначала что-то попадает на дно банки и постепенно она заполняется все новым и новым содержимым.
Вернёмся к нашему факториалу. Когда мы вызываем factorial(5), в стеке последовательно накапливаются вызовы:
На самой верхушке стека будет функция factorial(1), которая возвращает 1. Система вызывает её, получает в результате единицу, следом вызывается функция factorial(2), затем factorial(3) и так до исходной функции factorial(5).
Но стек вызовов не бесконечен. В каждом языке программирования накладываются свои ограничения на стек. К тому же в самой операционной системе есть собственные ограничения на стек вызовов.
Таким образом, если у вас будет слишком много вызовов функции, то произойдёт переполнение стека (stack overflow), что приведёт к аварийному завершению процесса.
Предел рекурсии
В каждом языке программирования есть свои ограничения, и в Python стек по умолчанию ограничен 1000 вызовами.
Проверим это:
Это означает, что максимальная глубина рекурсии — 1000 вызовов.
Попробуем вычислить факториал 1000:
И получим ошибку: «RecursionError: maximum recursion depth exceeded in comparison». Интерпретатор говорит: «Стоп, ты вызвал функцию слишком много раз!»
Ограничение в 1000 вызовов — не прихоть разработчиков Python. Это защита от переполнения стека.
Представьте, что у вас есть функция с ошибкой:
Без ограничения эта функция вызывала бы себя бесконечно, пока не съела бы всю доступную память и не убила вашу программу (а может, и всю систему).
Ограничение в 1000 вызовов — это разумный компромисс между безопасностью и практичностью.
Увеличение предела рекурсии
Но как быть, если нам уж очень хочется посмотреть, какой же там будет факториал у числа 1000?
Есть два подхода:
- Увеличить глубину рекурсии
- Использовать мемоизацию (об этом в следующей статье)
Начнём мы с самого простого, но не самого эффективного — увеличения глубины рекурсии. Да, самое очевидное, что может прийти на ум — просто убрать ограничения, установленные разработчиками языка, тем более что они предоставили такую удобную функцию для этого.
Этой функцией является setrecursionlimit() из того же модуля sys.
Эта функция принимает целое число и изменяет внутренний счётчик, который отслеживает глубину рекурсии.
Теперь программа работает! Мы получим огромное число — факториал тысячи.
Но не спешите радоваться.
Увеличение глубины рекурсии похоже на езду без ремня безопасности. Технически можно, но очень рискованно.
Проблема 1: Segmentation Fault (ошибка сегментации)
Операционная система ограничивает размер стека для каждого процесса. Это жёсткое ограничение, и его нельзя обойти из Python. В лучшем случае вы получите ошибку от Python. В худшем — операционная система убьёт ваш процесс с сообщением «Segmentation Fault». Это серьёзная системная ошибка, которая означает, что ваша программа попыталась обратиться к памяти, к которой у неё нет доступа.
Проблема 2: Out of Memory (нехватка памяти)
Каждый вызов функции занимает место в памяти. При глубокой рекурсии память быстро заканчивается.
Что произойдёт:
- Если памяти много — программа будет работать очень медленно
- Если памяти мало — программа завершится с ошибкой Out of Memory
На практике Python обычно ловит эти ошибки раньше и выдаёт RecursionError, но полагаться на это не стоит.
Проблема 3: Скорость работы
Даже если памяти хватит, глубокая рекурсия работает медленно. Каждый вызов функции — это накладные расходы на сохранение контекста, создание нового фрейма в стеке и так далее.
Для вычисления факториала 100 000 рекурсивным способом понадобится много времени, даже если вы увеличите лимит.
Когда можно увеличивать лимит?
Увеличивать лимит рекурсии имеет смысл только если:
- Вы точно знаете, что глубина рекурсии будет немного больше 1000 (например, 1200-1500)
- У вас есть базовый случай, и функция точно завершится
- Вы понимаете, что делаете, и готовы к возможным проблемам
Для задания 16 ЕГЭ увеличение лимита до 2000-3000 обычно безопасно. Но если требуется большая глубина — лучше использовать методы оптимизации рекурсии.
Вместо бездумного увеличения лимита рекурсии стоит:
- Проверить, можно ли переписать алгоритм, используя итеративный подход
- Оптимизировать рекурсию, используя мемоизацию
Но об оптимизации рекурсии, кешировании, мемоизации и об одном очень полезном декораторе мы поговорим уже в следующей статье.