❗РЕКОМЕНДАЦИЯ К ПРОЧТЕНИЮ 🔽
→ Данный материал продолжает тему изучения рекурсивных функций и является прямым продолжением предыдущих частей (ЧАСТЬ 1 и ЧАСТЬ 2) 🔽
✅ В этой статье будет подробно рассмотрена типовая задача формата ЕГЭ, решение которой будет представлено двумя способами:
- Аналитический (с помощью листка бумаги или Paint)
- Программный (с помощью написания алгоритма на Python)
🚥HERE WE GO →
УСЛОВИЕ ЗАДАЧИ
Необходимо 2 - 3 раза внимательно прочитать условие задачи ⤵
После изучения данного ⇪ материала важно выделить главные моменты для дальнейшего успешного решения →
ВАЖНЫЕ МОМЕНТЫ ИЗ УСЛОВИЯ
В данной задаче удалось выделить 3 важных момента ⤵
1. РЕКУРРЕНТНАЯ ФОРМУЛА
Рекуррентная формула (соотношение) — это алгоритм, по которому каждое новое значение считается через предыдущие значения.
🚨В условии задачи необходимо определить, какие данные задают основную формулу рекурсивной функции. Так как именно по этой формуле будет выполняться алгоритм и решаться задача →
- F(n) = F(n - 1) * n
2. УСЛОВИЕ ОСТАНОВКИ РЕКУРСИВНОЙ ФУНКЦИИ
Условие остановки (условие выхода) — это условие, при котором функция перестаёт вызывать саму себя
Без условия остановки рекурсивной функции она будет вызывать саму себя бесконечное количество раз. Что приведёт к данной ошибке:
❌ RecursionError: maximum recursion depth exceeded — «Ошибка рекурсии: превышена максимальная глубина рекурсии»
- F(1) = 1
3. ЧТО НУЖНО НАЙТИ В ЗАДАЧЕ
→ В данной задаче необходимо определить чему будет равно значение функции F(5)
- F(5) — ?
👏 Good! Теперь можно приступать к решению нашей задачи, первым способом →
РЕШЕНИЕ АНАЛИТИЧЕСКИМ МЕТОДОМ
Для решения задачи необходимо выполнить алгоритм, записанный в условии ⤵
🔻ПЕРВЫЙ ВЫЗОВ ФУНКЦИИ
По условию задачи необходимо определить значение функции F(5)
Это значит, что в основную формулу F(n) = F(n - 1) * n, вместо переменной n нужно подставить число 5 →
→ тогда, F(5) — будет первым действием функции или первым рекурсивным вызовом ⤵
- F(5) — первое выполнение рекурсивной функции F с аргументом, равным 5
Согласно исходному алгоритму, после вызова F(5), рекурсивная функция должна вызвать функцию F(4), умноженную на 5:
- F(5) = F(5 - 1) * 5 = F(4) * 5
После записи данной строки ⇪ появилась ещё одна функция: F(4) — это значит, что функция F вызвала саму себя, но уже с другим аргументом ⤵
→ Следовательно, для продолжения выполнения алгоритма необходимо рассмотреть функцию F(4) ⤵
🔻ВТОРОЙ ВЫЗОВ ФУНКЦИИ
Второй вызов функции будет выполнен для аргумента n = 4
- F(4) — выполнение рекурсивной функции F с аргументом, равным 4
Согласно рекурсивному алгоритму, после вызова F(4), функция должна вызвать функцию F(3), умноженную на 4 →
- F(4) = F(4 - 1) * 4 = F(3) * 4
❓Что произойдет с функцией F(5)
— Функция F(5) остаётся в ожидании завершения, так как был выполнен только её вызов без получения конкретного результата.
Для продолжения выполнения алгоритма необходимо рассмотреть функцию F(3) ⤵
🔻ТРЕТИЙ ВЫЗОВ ФУНКЦИИ
Третий вызов функции будет выполнен для аргумента n = 3
- F(3) — выполнение рекурсивной функции F с аргументом, равным 3
Согласно рекурсивному алгоритму, после вызова F(3), функция должна вызвать функцию F(2), умноженную на 3 →
- F(3) = F(3 - 1) * 3 = F(2) * 3
Что произойдет с функциями F(5) и F(4)?
— Функции F(5) и F(4) будут ожидать своего завершения
Для продолжения выполнения алгоритма необходимо рассмотреть функцию F(2) ⤵
🔻ЧЕТВЁРТЫЙ ВЫЗОВ ФУНКЦИИ
Четвёртый вызов функции будет выполнен для аргумента n = 2
- F(2) — выполнение рекурсивной функции F с аргументом, равным 2
Согласно рекурсивному алгоритму, после вызова F(2), функция должна вызвать функцию F(1), умноженную на 2 →
- F(2) = F(2 - 1) * 2 = F(1) * 2
Что произойдет с функциями F(5), F(4), F(3), F(2)?
— Функции F(5), F(4), F(3), F(2) будут ожидать своего завершения
Для продолжения выполнения алгоритма необходимо рассмотреть функцию F(1) ⤵
🔻ПЯТЫЙ ВЫЗОВ ФУНКЦИИ
Пятый вызов функции будет выполнен для аргумента n = 1
- F(1) — выполнение рекурсивной функции F с аргументом, равным 1
❕ВАЖНЫЙ МОМЕНТ:
Необходимо ещё раз внимательно посмотреть на условие задачи и обратить внимание на следующее соотношение:
- F(1) = 1
→ ИМЕННО НА ПЯТОМ ВЫЗОВЕ СРАБОТАЕТ УСЛОВИЕ ОСТАНОВКИ (ВЫХОДА) ИЗ РЕКУРСИВНОГО АЛГОРИТМА
❕Это означает, что дальнейшие рекурсивные вызовы функции F больше выполняться не будут.
Прежде чем продолжить решение задачи, подведём небольшие итоги ⤵
🔸ПРОМЕЖУТОЧНЫЕ ИТОГИ
- Рекурсивная функция F выполнила 5 вызовов с различными аргументами: F(5) → F(4) → F(3) → F(2) → F(1)
- Функции F(5), F(4), F(3), F(2) всё ещё ожидают своего завершения
- На последнем вызове F(1) сработало условие остановки. Теперь значение функции F(1) = 1.
❓Что произойдёт дальше →
➡ ВЫХОД ИЗ РЕКУРСИИ
После пятого вызова, рекурсивная функция должна остановиться. Функция F(1) примет значение, равное 1. Куда будет передано это значение?
❕ВАЖНЫЙ МОМЕНТ:
— Функции F(5), F(4), F(3), F(2) до сих пор ожидают своего завершения.
Для завершения функции F(2) необходимо значение функции F(1) умножить на 2. То есть функция F(2) должна получить конкретное значение от F(1) →
→ ЗНАЧЕНИЕ, ПОЛУЧЕННОЕ ПОСЛЕ ВЫПОЛНЕНИЯ ВЫЗОВА F(1), БУДЕТ ПЕРЕДАНО ОБРАТНО В ПРЕДЫДУЩИЕ ВЫЗОВЫ ФУНКЦИИ ⤵
❕После пятого выполнения рекурсивной функции F(1), произойдет остановка рекурсивного алгоритма. Значение из функции F(1) будет передано "вверх" (обратно) в предыдущий вызов F(2) →
- F(2) = F(1) * 2 = 1 * 2 = 2
Теперь необходимо завершить каждый предыдущий вызов функции F ⤵
🔺ЗАВЕРШЕНИЕ ЧЕТВЁРТОГО ВЫЗОВА
Для завершения F(2) необходимо значение функции F(1) умножить на 2 →
- F(2) = F(1) * 2 = 1 * 2 = 2
Четвёртый вызов рекурсивной функции будет завершён. Функция F(2) передаст в предыдущие вызовы, значение = 2 ⤵
— Функции F(5), F(4), F(3) до сих пор ожидают своего завершения. Функции F(1), F(2) завершили свою работу.
🔺ЗАВЕРШЕНИЕ ТРЕТЬЕГО ВЫЗОВА
Для завершения F(3) необходимо значение функции F(2) умножить на 3 →
- F(3) = F(2) * 3 = 2 * 3 = 6
Третий вызов рекурсивной функции будет завершён. Функция F(3) передаст в предыдущие вызовы, значение = 6 ⤵
— Функции F(5), F(4) до сих пор ожидают своего завершения. Функции F(1), F(2), F(3) завершили свою работу.
🔺ЗАВЕРШЕНИЕ ВТОРОГО ВЫЗОВА
→ На Для завершения F(3) необходимо значение функции F(2) умножить на 3
Второй вызов рекурсивной функции будет завершён. Функция F(4) передаст в предыдущие вызовы, значение = 24
- F(4) = F(3) * 4 = 6 * 4 = 24
— Функция F(5) до сих пор ожидает своего завершения. Функции F(1), F(2), F(3) и F(4) завершили свою работу.
🔺ЗАВЕРШЕНИЕ РЕКУРСИВНОЙ ФУНКЦИИ
Остался последний вызов — функция F(5)
Вызовы: F(1), F(2), F(3) и F(4) уже завершили свою работу.
Для завершения вызова F(5) необходимо результат функции F(4) умножить на 5
F(5) = F(4) * 5 = 24 * 5 = 120
— Функции F(1), F(2), F(3), F(4) и F(5) завершили свою работу. Больше текущих вызовов нет, значит рекурсивная функция завершит свою работу ⤵
→ В результате выполнения алгоритма и вызова функции F(5) получится число 120
120 — ответ к задаче
⭐ Отлично! Теперь попробуем написать код в Python для решения данной задачи →
РЕШЕНИЕ ЗАДАНИЯ ЧЕРЕЗ PYTHON
Перед написанием алгоритма нужно ещё взглянуть на условие задачи →
Решение будет включать в себя несколько основных этапов 🔽
- СОЗДАНИЕ ФУНКЦИИ
- УСЛОВИЕ ОСТАНОВКИ
- РЕКУРСИВНЫЙ ВЫЗОВ
- ВЫЗОВ ФУНКЦИИ В ОСНОВНОЙ ПРОГРАММЕ
Переходим к первому этапу →
🔻СОЗДАНИЕ ФУНКЦИИ
Для решения задачи необходимо создать функцию, в которой и будет реализован рекурсивный алгоритм ⤵
→ Что используется в программе:
- def — служебная команда для создания функций в Python
- F — имя функции
- n — аргумент функции (переменная, которая будет использоваться только внутри функции)
Следующий этап ↷
🔻УСЛОВИЕ ОСТАНОВКИ
Необходимо всегда держать в голове базовое условие для остановки рекурсивной функции →
❕Без этого условия функция будет вызывать саму себя бесконечное количество раз, что приведёт к данной ошибке:
❌ RecursionError: maximum recursion depth exceeded — «Ошибка рекурсии: превышена максимальная глубина рекурсии»
→ В данной задаче условием для остановки рекурсии является данная строка F(1) = 1 🔽
→ Данная строка означает, что когда функция вызовет саму себя с аргументом 1, дальнейшие вызовы прекратятся и функция вернёт значение = 1 🔽
→ Что используется в программе:
- if — служебная команда для создания условий в Python
- n == 1 — условие для выхода из рекурсивной функции
- return 1 — значение, которые вернёт функция F(1) после своего завершения
Следующий этап ↷
🔻РЕКУРСИВНЫЙ ВЫЗОВ
Алгоритм, при котором функция вызывает саму себя →
→ Что используется в программе:
- n > 1 — условие, при котором должен произойти рекурсивный вызов
- F(n - 1) * n — рекурсивный вызов функции (F) с новым аргументом (n - 1)
Следующий этап ↷
🔻ВЫЗОВ ФУНКЦИИ В ОСНОВНОЙ ПРОГРАММЕ
Чтобы функция выполнилась её необходимо вызвать (запустить) в основной программе →
→ Что используется в программе:
- print() — служебная команда Python, для отображения результата в консоли
После запуска программы, на экране консоли отобразится число:
120
⭐ Отлично! Полученный ответ совпадает с ответом из аналитического решения. Значит, алгоритм работает!
НЕКОТОРЫЕ ИНТЕРЕСНЫЕ МОМЕНТЫ ПО РЕШЕНИЮ
Для лучшего понимания работы алгоритма →
❶ ЧТО БУДЕТ, ЕСЛИ ПРОСТО ВЫЗВАТЬ ФУНКЦИЮ, БЕЗ КОМАНДЫ PRINT?
Пояснение:
📌 Функция F(n) выполняет заданный алгоритм, но сама по себе не выводит результат на экран. Для отображения необходимо использовать команду print, иначе программа сработает без отображения результата в консоль.
❷ КАКАЯ ЧАСТЬ КОДА ОТНОСИТСЯ К ФУНКЦИИ, КАКАЯ К ОСНОВНОЙ ПРОГРАММЕ?
Пояснение:
- Весь код, что с отступом внутри def — тело функции (относится только к функции)
- Весь код, который расположен на одном уровне с def — основная программа (не относится к функции)
Функция — это описание определённых действий, а основная программа — их выполнение.
⚡Прекрасная работа! Теперь, разобравшись с базовыми примерами рекурсивной функцией в Python, можно приступить к решению более сложных заданий ↷