❗ПЕРЕД ПРОЧТЕНИЕМ НАСТОЯТЕЛЬНО РЕКОМЕНДУЮ ОЗНАКОМИТЬСЯ С ПЕРВОЙ ЧАСТЬЮ МАТЕРИАЛА ⤵
🚩В ПЕРВОЙ ЧАСТИ ⇪ материала были рассмотрены следующие темы:
- Что такое функция и как создать функцию в Python
- Оператор return и его роль в функциях
- Примеры многократного вызова функции
- Основное определение рекурсивной функции и её смысл
→ Следующий этап — научиться разрабатывать рекурсивные функции в Python ⤵
СОЗДАНИЕ РЕКУРСИВНОЙ ФУНЦИИ В PYTHON
👉 Для создания рекурсивной функции в Python необходимо воспользоваться следующим определением:
Рекурсивная функция — это функция, которая вызывает саму себя.
→ Попробуем создать рекурсивную функцию, руководствуясь данным ⇪ определением
Нужно вспомнить алгоритм создания функции в Python, который был описан ранее в этой статье ⤵
→ Создадим функцию def и назовём её INF. Чтобы функция вызвала саму себя, запишем функцию INF внутри функции INF.
Далее необходимо вызвать функцию в основной программе и запустить код 🔥
После запуска появляется данная ошибка:
❌ RecursionError: maximum recursion depth exceeded — «Ошибка рекурсии: превышена максимальная глубина рекурсии»
- Что это значит?
— Функция вызывает саму себя слишком много раз (или бесконечно ♾), и Python останавливает выполнение, так как память компьютера ограничена.
⭐ Отлично! Значит нам удалось всё - таки создать рекурсивную функцию! Функция INF() вызывает саму себя (правда, слишком много раз 😳).
- Как исправить бесконечный вызов рекурсивной функции?
— Записать условие для выхода (остановки) рекурсивной функции ⤵
📍Условие остановки (условие выхода) — это условие, при котором функция перестаёт вызывать саму себя →
РЕКУРСИВНАЯ ФУНКЦИИ С УСЛОВИЕМ ВЫХОДА
Без условия выхода (остановки) рекурсия будет выполняться бесконечно
→ Создадим рекурсивную функцию four, которая будет обязательно содержать условие для остановки (выхода) из функции ↷
📍Далее рассмотрим работу данной программы шаг за шагом, уделяя внимание каждому этапу ⤵
1️⃣ШАГ ПЕРВЫЙ | Вызов функции
На данном этапе Python должен осуществить вызов функции four →
❕Важный момент:
— При запуске программы Python читает код строку за строкой, сверху - вниз ↓ (но не всегда линейно)
→ Первое, что встретит интерпретатор — строка def four(x), то есть объявление функции. Но, Python не выполнит запуск данной функции, так как она ещё не была вызвана в основной программе ⤵
→ Поэтому Python пропустит функцию four и перейдёт к коду, после функции → где как раз и записан вызов данной функции с аргументом х равным = 20.
- four(20) — первая команда, которую выполнит Python
Что произойдёт после вызова функции four? →
2️⃣ ШАГ ВТОРОЙ | Обработка функции
→ После вызова функции Python переходит к выполнению её тела (код внутри функции). В первую очередь определяется, какие аргументы принимает функция. В данном случае в неё передаётся только один аргумент — переменная x ⤵
3️⃣ ШАГ ТРЕТИЙ | Код внутри функции
→ Первая строчка кода внутри функции — оператор if
Оператор if проверяет заданное условие. Если условие истинно True, то выполняется определённый набор действий.
- if x == 0: — если переменная х равна 0, то ...
В данный момент условие не выполнится, так как x = 20 ⤵
Следовательно, Python пропустит код внутри if и перейдёт к следующей строке →
4️⃣ ШАГ ЧЕТВЁРТЫЙ | Вывод (х) в консоль
После условия if записана команда print(x). Python выполнит эту команду и выведет текущее значение переменной х = 20 в консоль ⤵
В результате данного шага на экране появится число — 20 →
5️⃣ ШАГ ПЯТЫЙ | РЕКУРСИЯ
💢Именно на этом шаге и произойдёт рекурсивный вызов функции (four)
→ После команды print Python перейдёт к следующей строке — four(x - 5)
Это и есть повторный вызов той же самой функции в теле функции ⤵
→ В результате выполнения строки four(x - 5) произойдёт повторный вызов функции four, с аргументом х = 15.
Рекурсивная функция — это функция, которая вызывает саму себя.
❕ВАЖНЫЕ ВОПРОСЫ:
- Почему (х) теперь равен 15?
— Так как текущее значение переменной х = 20, а в функцию передаётся параметр х - 5 следовательно: 20 - 5 = 15
- Что произойдёт с функцией four, которая была вызвана в первый раз? Она исчезнет?
— Каждый рекурсивный вызов это новый, отдельный вызов функции со своим состоянием. Все они висят в стеке вызовов, ожидая завершения вложенного вызова ⤵
🔒Python ограничивает размер стека (обычно ~1000 вызовов).
Стек вызовов (call stack) в Python — это структура данных, в которой Python хранит информацию о вызванных, но ещё не завершённых функциях.
→ ПРОДОЛЖАЕМ РАБОТУ С РЕКУРСИВНЫМИ ВЫЗОВАМИ ФУНКЦИИ ⤵
- ВТОРОЙ ВЫЗОВ (х = 15)
→ Вновь Python начнёт обрабатывать функцию four, только теперь с новым аргументом х = 15 ⤵
→ Условие if не будет выполнено, поэтому интерпретатор перейдёт к команде print(x). На экране консоли появится число 15 — текущее значение переменной х ⤵
После вывода текущего значения х, Python перейдёт к следующей строке внутри функции →
- four(x - 5) — что означает, очередной рекурсивный вызов функции four ⤵
- ТРЕТИЙ ВЫЗОВ (х = 10)
→ Вновь Python начнёт обрабатывать функцию four, только теперь с новым аргументом х = 10 ⤵
- Вывод на экран текущего значения переменной х ⤵
- Очередной рекурсивный вызов функции four ⤵
- ЧЕТВЁРТЫЙ ВЫЗОВ (х = 10)
→ Вновь обработка функции four, только теперь с новым аргументом х = 5 ⤵
- Вывод на экран текущего значения переменной х ⤵
- Очередной рекурсивный вызов функции four ⤵
- ПЯТЫЙ ВЫЗОВ (х = 0)
→ Вновь обработка функции four, только теперь с новым аргументом х = 0 ⤵
💢УСЛОВИЕ ВНУТРИ if ВЫПОЛНЯЕТСЯ ↷
Поскольку текущее значение переменной x равно 0 →
- if x == 0 — True (Истина)
Условие выполняется, поэтому Python перейдёт к коду, внутри if
- return print('W')
Данная строка завершает выполнение текущего вызова функции four и выводит символ W в консоль ⤵
⭐ Отлично! Python выполнил команду return внутри функции four.
- Что дальше? Что будет после команды return?
— Команда return завершает выполнение текущей функции four(0)
- Что будет с предыдущими вызванными функциями: four(5), four(10) .. ?
— Все эти функции тоже будут завершены
→ Однако это происходит не потому, что завершилась последняя функция, а из-за того, что в каждой функции выполнены все строки кода.
❕ВАЖНЫЙ МОМЕНТ
— return не останавливает все функции сразу ⤵
→ Шаги выполнения функции four(0):
- Вызов four(0) ⤵
→ печатает W
→ return → выходит из four(0) - Возврат в four(5) ⤵
После строки four(x - 5) больше кода нет ✖
→ функция завершается автоматически - Те же действия и для функций:
four(10)
four(15)
four(20)
→ Когда последний вызов функции four(0) будет завершён, Python перейдёт к предыдущему вызову функции — four(5) ⤵
→ После завершения функции four(5), Python перейдёт к предыдущему вызову — four(10) ⤵
→ После завершения функции four(10), Python перейдёт к предыдущему вызову — four(15) ⤵
→ После возврата к самому первому вызову four(20) выполнение программы завершится 🔚
❓Почему в рекурсивной функции four() нет 'RecursionError'
— Есть условие выхода (if x == 0)
Условие при котором функция перестаёт вызывать саму себя
— Переменная x уменьшается: four(x - 20), four(x - 15) и так далее
Что и позволяет достичь условия выхода
➡️РЕКУРСИЯ КОРРЕКТНАЯ И БЕЗОПАСНАЯ ✅
⚡Прекрасная работа! Теперь, разобравшись с рекурсивной функцией в Python, можно приступить к решению заданий формата ЕГЭ и не только ↷