→ Данный материал продолжает тему изучения рекурсивных функций и является прямым продолжением предыдущих частей (ЧАСТЬ 1, ЧАСТЬ 2, ЧАСТЬ 3) 🔽
✅ В этой статье представлен подробный разбор ещё одной задачи формата ЕГЭ по информатике. Данная задача отличается повышенной сложностью: для её решения требуются дополнительные знания по работе с библиотеками языка Python.
🚥HERE WE GO →
УСЛОВИЕ ЗАДАЧИ
Необходимо 2 - 3 раза внимательно прочитать условие задачи ⤵
После прочтения данного ⇪ материала важно выделить ключевые моменты, которые понадобятся для решения →
КЛЮЧЕВЫЕ МОМЕНТЫ ИЗ УСЛОВИЯ
В данной задаче удалось выделить 3 ключевых пункта ⤵
- РЕКУРРЕНТНАЯ ФОРМУЛА
Рекуррентная формула (соотношение) — это алгоритм в рекурсивной функции, по которому каждое новое значение считается через предыдущие значения.
🚨В условии задачи нужно найти данные, которые задают основную формулу рекурсивной функции. Эта формула лежит в основе алгоритма и используется для решения задачи →
В данной задаче записана следующая рекуррентная формула:
- F(n) = n * F(n - 1), если n > 1
Переходим к следующему важному пункту из условия задачи ⤵
- УСЛОВИЕ ДЛЯ ОСТАНОВКИ РЕКУРСИВНОЙ ФУНКЦИИ
Условие остановки (условие выхода) — это условие, при котором функция перестаёт вызывать саму себя
🚨Без условия остановки рекурсивной функции она будет вызывать саму себя бесконечное количество раз.
В данной задаче используется следующее условие для выхода из рекурсии:
- F(n) = 1, при n = 1
Переходим к следующему важному пункту из условия задачи ⤵
- ГЛАВНЫЙ ВОПРОС ИЛИ ЧТО НУЖНО НАЙТИ В ЗАДАЧЕ
→ В данной задаче необходимо определить чему будет равно значение выражения F(2023) / F(2020) ⤵
F(2023) — значение функции F, при n = 2023
F(2020) — значение функции F, при n = 2020
- F(2023) / F(2020) — ?
👏 Good! Теперь переходим к решению задачи →
РЕШЕНИЕ ЗАДАНИЯ ЧЕРЕЗ PYTHON
Сначала проанализируем, как работает данная рекурсивная функция, а уже затем будем записывать программный код для решения задачи 🔽
→ Анализ рекурсивных вызовов функции F показывает: на каждом шаге текущее значение n умножается на результат предыдущего вызова F:
- n = 1 → F = 1
↳ n = 2 → F = 2 * 1 = 2
↳ n = 3 → F = 3 * 2 = 6 и так далее
→ Данный алгоритм соответствует нахождению факториала числа.
Факториал числа — это произведение всех натуральных чисел от 1 до n, включая само n.
4! = 1 · 2 · 3 · 4 = 24
☑ Зафиксировали данную информацию, она ещё пригодится при решении задания.
КОД НА PYTHON
Решение будет включать в себя 4 основных этапа 🔽
- СОЗДАНИЕ ФУНКЦИИ
- УСЛОВИЕ ОСТАНОВКИ
- РЕКУРСИВНЫЙ ВЫЗОВ
- ВЫЗОВ ФУНКЦИИ В ОСНОВНОЙ ПРОГРАММЕ
Переходим к первому этапу →
🔻СОЗДАНИЕ ФУНКЦИИ
Для решения задачи необходимо создать функцию, в которой и будет реализован рекурсивный алгоритм ⤵
Следующий этап ↷
🔻УСЛОВИЕ ОСТАНОВКИ
Необходимо всегда держать в голове базовое условие для остановки рекурсивной функции →
❕Если не записать данное условие, функция будет вызывать себя бесконечное количество раз — рекурсия не завершится ⤵
Следующий этап ↷
🔻РЕКУРСИВНЫЙ ВЫЗОВ
Алгоритм, при котором функция вызывает саму себя →
Следующий этап ↷
🔻ВЫЗОВ ФУНКЦИИ В ОСНОВНОЙ ПРОГРАММЕ
Для выполнения функции её необходимо вызвать (запустить) в теле основной программы →
→ Программа запущена ... НО
После запуска программы появилась данная ошибка:
❌ RecursionError: maximum recursion depth exceeded — «Ошибка рекурсии: превышена максимальная глубина рекурсии»
❕ПОЧЕМУ ВОЗНИКЛА ДАННАЯ ОШИБКА?
Для ответа на данный вопрос, необходимо вспомнить основное определение рекурсивной функции:
Рекурсивная функция — это функция, которая вызывает саму себя.
Каждый новый вызов функции необходимо где-то хранить, так как все последующие вызовы нужны для завершения всей функции →
📁 Место для хранения всех текущих вызовов функции — СТЕК
- (англ. stack) — в буквальном переводе означает «стопка» или «куча»
→ Каждый новый вызов рекурсии добавляет новый «элемент» в стек вызовов программы ⤵
⚠ ВАЖНЫЙ МОМЕНТ
Стек вызовов ограничен по объёму.
Python ограничивает число вложенных вызовов рекурсивной функции, чтобы избежать переполнения стека и аварийного завершения программы.
→ Это ограничение и называется лимитом рекурсии.
Если функция попытается вызвать себя больше раз, чем разрешено лимитом, возникнет данная ошибка:
❌ RecursionError: maximum recursion depth exceeded
→ По умолчанию лимит рекурсии в Python составляет 1000 вызовов — это максимальная глубина вложенных вызовов функций, которую допускает интерпретатор.
❓СКОЛЬКО РАЗ БУДЕТ ВЫЗВАНА ФУНКЦИЯ В ДАННОЙ ПРОГРАММЕ
Для ответа на данный вопрос необходимо посмотреть на рекуррентную формулу:
F(n) = n * F(n - 1)
Это значит, что каждый новый вызов происходит через одну итерацию (+1)
→ Следовательно, количество вызовов равно количеству функций ⤵
→ При вызове F(2023) будет 2023 раза выполнена функция + F(2020) ещё 2020 вызовов →
Итого: 2023 + 2020 = 4 043 ВЫЗОВА РЕКУРСИВНОЙ ФУНКЦИИ
❗И это значение больше, чем установленный лимит Python в 1000 вызовов
⚠ НО! Максимальная глубина рекурсии будет равна = 2023
- Как устранить проблему с ограничением лимита рекурсии, для успешного выполнения исходной задачи?
— Необходимо самостоятельно увеличить лимит рекурсии с помощью встроенного модуля →
УВЕЛИЧЕНИЕ ЛИМИТА РЕКУРСИИ В PYTHON
С помощью подключения встроенного модуля import sys →
Для устранения проблемы с превышением лимита рекурсии необходимо воспользоваться дополнительными модулями в Python ⤵
import
import — это команда, которая позволяет использовать готовый код из других файлов или библиотек в вашей программе.
Пример с подключением модулей math и random ⤵
- Модуль random — встроенная библиотека Python для генерации псевдослучайных чисел
import sys
import sys подключает специальный встроенный модуль sys. Данный модуль обеспечивает доступ к настройкам самого Python
Пример с подключением модуля sys ⤵
- sys.version — команда из встроенного модуля sys, служит для определения текущей версии интерпретатора Python.
- sys.platform — команда из встроенного модуля sys, служит для определения версии операционной системы (ОС).
⚠ ВАЖНЫЙ МОМЕНТ
→ Модуль import sys содержит команду, которая позволяет увеличить лимит рекурсии в Python
- sys.setrecursionlimit — это функция из стандартного модуля sys, которая позволяет изменять максимальную глубину рекурсии.
- sys.getrecursionlimit — это встроенная функция из модуля sys в Python, которая возвращает текущее значение максимальной глубины рекурсии.
Теперь, необходимо добавить модуль sys в наше решение и тем самым, увеличить лимит рекурсивной функции →
🔥ИТОГОВОЕ РЕШЕНИЕ ИСХОДНОЙ ЗАДАЧИ
Перед итоговым решением нужно ещё раз посмотреть на условие задачи ⤵
УСЛОВИЕ 🔽
И переходим к самому главному →
РЕШЕНИЕ 🔽
⭐ Отлично! Ошибки больше нет, алгоритм работает!
Ответ: 8266912626.0
⚠ ВАЖНЫЙ МОМЕНТ:
8266912626.0 — не совсем корректный ответ для данной задачи. Далее будет объяснение почему так и какой ответ будет корректным ⤵
→ ПОДВЕДЁМ ПРОМЕЖУТОЧНЫЕ ИТОГИ ПО ПРОЙДЕННОМУ МАТЕРИАЛУ:
- Необходимо всегда записывать условие для остановки рекурсивной функции, иначе функция будет выполняться бесконечно.
- Максимальная глубина рекурсивной функции в Python ∼ 1000 вызовов.
- Каждый новый вызов рекурсивной функции добавляется в стек, стек ограничен по объёму.
- import — команда для подключения дополнительных модулей в Python.
- sys.getrecursionlimit — функция из модуля sys, чтобы узнать текущий лимит рекурсии.
- sys.setrecursionlimit — функция из модуля sys, позволяет изменить максимальную глубину рекурсии.
Теперь можно выделить несколько интересных моментов из решения данной задачи ⤵
НЕКОТОРЫЕ ИНТЕРЕСНЫЕ МОМЕНТЫ ПО РЕШЕНИЮ
Для лучшего понимания работы алгоритма →
❶ ПОЧЕМУ ОТВЕТ ЗАПИСАН В ДРОБНОМ ВИДЕ?
- Необходимо внимательно посмотреть на вопрос из условия задачи:
Чему равно значения выражения F(2023) / F(2020)?
→ Условие задачи содержит знак /, в Python это оператор деления. Данный оператор возвращает дробное число.
Пояснение:
📌 Чтобы результат был целым (без дробной части), необходимо заменить знак / на оператор целочисленного деления //
❷ ГДЕ ЗАПИСЫВАТЬ import В ПРОГРАММЕ?
Пояснение:
📌 Импорт (import) модулей следует размещать сразу после комментариев (если они присутствуют) и до остального кода.
→ Это необходимо, поскольку функции и библиотеки из импортированных модулей становятся доступны только после их подключения.
- ЕСЛИ ИМПОРТИРУЕМЫЕ МОДУЛИ РАЗМЕСТИТЬ В КОНЦЕ ПРОГРАММЫ?
Ответ:
— Появляется вероятность возникновения ошибок в программе.
→ Например, если для решения задачи нужно увеличить лимит рекурсии через import sys, модуль следует импортировать до вызова рекурсивной функции. Если сделать это позже, программа выдаст ошибку ⤵
В данном примере ⇪ программа сначала выполнит рекурсивные функции F(2023) и F(2020). Лимит рекурсии будет превышен. И лишь потом, импортируется необходимый модуль import sys.
❸ КАКОЕ ЧИСЛО ВЫБРАТЬ ДЛЯ УВЕЛИЧЕНИЯ ЛИМИТА?
Если уменьшить в исходной программе лимит до 2000, то программа будет работать →
Пояснение:
📌 От 2000 до 10000 — подходит для большинства практических задач (обход деревьев, графы средней глубины, вычисление факториала до 4000 и так далее).
✅ Данный диапазон является безопасным.
ЕСЛИ ВЫБРАТЬ ГОРАЗДО БОЛЬШИЙ ЛИМИТ ДЛЯ РЕКУРСИИ?
— Установка слишком высокого значения ( > 10 000) может привести к тому, что Python аварийно завершит работу.
На экране появится ошибка операционной системы (Segmentation Fault), так как стек процесса превысит лимит памяти, выделенный ОС.
🕔 Либо программа будет работать гораздо более длительный промежуток времени.
- Как быть в таком случае?
— Часто лучшим решением является не увеличение лимита, а переписывание рекурсивного алгоритма на итеративный (с использованием циклов или мемоизации), что более безопасно и эффективно.
- Что такое мемоизация?
Мемоизация — это сохранение результатов выполнения функции для конкретных входных аргументов. Если функция вызывается снова с теми же аргументами, вместо повторного вычисления результат просто извлекается из кэша.