Рекурсия 1: базовый принцип и рекурсивные функции
Цели и задачи
- Цель по SMART: к концу урока научиться распознавать базовый случай и рекурсивный шаг, составлять и тестировать простые рекурсивные функции на языке Python, а также объяснять ход их выполнения на конкретном примере.
- Познакомить учащихся с понятием рекурсии и отличиями рекурсивного алгоритма от алгоритма с циклом.
- Сформировать умение выделять базовый случай, рекурсивный шаг и условие завершения рекурсивной функции.
- Развивать алгоритмическое мышление, умение трассировать выполнение программы и находить причину бесконечной рекурсии.
- Воспитывать аккуратность при написании и тестировании программ, ответственность за результат совместной работы и интерес к применению рекурсии в программировании.
Планируемые результаты
Личностные
- Осознавать связь изучаемого материала с будущей профессиональной деятельностью в сфере программирования, анализа данных и разработки программ.
- Проявлять познавательный интерес к исследованию алгоритмов и самостоятельному поиску ошибок в коде.
- Понимать ценность аккуратного программирования и проверки результата на граничных случаях.
- Оценивать собственный уровень понимания темы и выбирать посильный уровень практического задания.
Метапредметные
- Планировать последовательность действий при разработке и тестировании рекурсивной функции.
- Читать программный код, выделять в нём условие выхода и повторяющийся фрагмент вычислений.
- Использовать электронную среду программирования для запуска кода, фиксации ошибок и проверки гипотез.
- Аргументированно объяснять партнёру ход выполнения программы и сравнивать рекурсивный и циклический способы решения.
Предметные
- Знать определения рекурсии, базового случая, рекурсивного шага и глубины рекурсии.
- Уметь составлять рекурсивные функции для вычисления суммы чисел от 1 до $n$ и факториала.
- Уметь пошагово прослеживать вызовы функции и записывать последовательность возвращаемых значений.
- Уметь обнаруживать отсутствие условия завершения и исправлять простые ошибки в рекурсивной программе.
- Владеть навыком тестирования программы на обычных и граничных значениях входных данных.
Универсальные учебные действия (УУД)
Личностные УУД
- Соотносить изучение рекурсии с личными образовательными и профессиональными интересами.
- Проявлять готовность преодолевать затруднение при анализе непривычного способа решения задачи.
- Осознавать ответственность за корректность собственного программного кода.
- Формировать привычку проверять программу на минимальных и особых значениях.
Регулятивные УУД
- Формулировать учебную цель на основе обнаруженного затруднения при выполнении задания.
- Планировать разработку функции через выделение базового случая и рекурсивного шага.
- Осуществлять пошаговый самоконтроль выполнения программы.
- Сравнивать результат с ожидаемым, находить ошибку и вносить коррективы.
- Оценивать степень самостоятельности и сложность выполненного задания.
Познавательные УУД
- Выделять существенные признаки рекурсивного алгоритма в программном коде.
- Строить дерево или цепочку вызовов функции для небольшого значения аргумента.
- Сравнивать рекурсивную и циклическую модели решения одной задачи.
- Моделировать выполнение программы в таблице трассировки.
- Искать информацию об ошибке переполнения стека по краткому сообщению среды программирования.
Коммуникативные УУД
- Объяснять партнёру назначение каждой части рекурсивной функции.
- Задавать уточняющие вопросы о порядке вызовов и возврата значений.
- Распределять роли в паре: разработчик, тестировщик и объясняющий.
- Аргументированно защищать выбор рекурсивного или циклического решения.
- Корректно давать обратную связь по принципу «две сильные стороны и один совет».
Подготовка учителя к уроку
- Подготовить компьютеры с запущенной средой программирования Python или браузерным интерпретатором; проверить запуск простых программ на всех рабочих местах.
- Создать на экране памятку: «Базовый случай → рекурсивный шаг → изменение аргумента в сторону базового случая».
- Подготовить презентацию с анимацией вызовов функции для примера $f(3)$ и схемой возврата значений.
- Распечатать карточки трёх уровней сложности: минимальный — трассировка, базовый — написание функции, повышенный — исправление и расширение программы; по одной карточке на каждого ученика.
- Подготовить лист самопроверки с пунктами: есть ли базовый случай, меняется ли аргумент, достигается ли условие остановки, проверен ли результат.
- Подготовить короткий фрагмент кода с бесконечной рекурсией и отдельный фрагмент с ошибкой в базовом случае.
- Разместить на доске тему урока, проблемный вопрос «Как функция может вызвать саму себя и всё же завершиться?» и критерии успешного решения.
- Подготовить таймер, стикеры трёх цветов для рефлексии и интерактивную доску или проектор.
- Организовать работу парами с возможностью выбора задания базового или повышенного уровня; предусмотреть подсказки для учащихся, которым нужна поддержка.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в практическую деятельность и создать проблемную ситуацию, требующую нового способа решения.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и проверяет готовность компьютеров: "Здравствуйте, ребята. Сегодня мы будем не просто слушать объяснение, а исследовать поведение программы. Откройте среду Python, создайте новый файл и приготовьте тетради для коротких схем. Работать будем в парах, но каждый должен понимать код и уметь объяснить его самостоятельно." | Включают компьютер, открывают среду Python, записывают дату и готовят тетрадь. |
2 мин | Учитель выводит на экран функцию: `def countdown(n): print(n); if n > 0: countdown(n - 1)` и спрашивает: "Что произойдёт после вызова `countdown(3)`? А что будет, если функция вызывает саму себя? Попробуйте предположить, почему программа не обязана работать бесконечно. Проблемный вопрос урока: как функция может вызвать саму себя и завершиться?" | Индивидуально формулируют предположение, затем обсуждают его в паре; отвечают: «Числа будут выведены от 3 до 0», «Нужна команда, которая остановит вызовы». |
Завершение этапа: учитель подводит итог: "Мы увидели, что функция может обращаться к самой себе, но пока не объяснили механизм остановки. Сейчас проверим, какие знания о функциях и условиях нам понадобятся, чтобы разобраться в этом поведении."
Этап 2. Актуализация знаний и физкультминутка (5 мин)
Цель этапа: восстановить знания о функциях, параметрах, условном операторе и организовать короткую двигательную паузу.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель проводит быструю проверку: "На экране четыре вопроса. Что такое параметр функции? Что делает `return`? Для чего нужен условный оператор `if`? Как изменится значение `n` после выполнения `n - 1`? Поднимите зелёную карточку, если ответ уверенный, жёлтую — если нужна подсказка. Обсудите последний вопрос с соседом и сформулируйте ответ точно." | Отвечают: «Параметр получает значение при вызове функции», «`return` возвращает результат», «`if` проверяет условие», «`n - 1` уменьшает значение на единицу». Показывают карточки самооценки. |
2 мин | Учитель проводит физкультминутку: "Встаньте рядом с рабочим местом. На слово «вызов» сделайте шаг вперёд, на слово «возврат» — шаг назад, на слово «условие» поднимите руки вверх. Выполним последовательность: вызов, вызов, условие, возврат, возврат. Теперь сядьте, выпрямите спину и продолжим работу." | Выполняют движения по инструкции, затем возвращаются к рабочим местам и проверяют посадку за компьютером. |
Завершение этапа: учитель подводит итог: "Мы вспомнили функции, параметры, условия и возврат результата. Эти элементы станут основой рекурсивной функции, поэтому теперь можно точно сформулировать, чего нам не хватает для решения проблемной ситуации."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: выявить признаки корректной рекурсии и совместно сформулировать цель практической работы.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает два фрагмента: `def f(n): return n + f(n - 1)` и `def f(n): if n == 0: return 0; return n + f(n - 1)`. Реплика: "Обе функции похожи, но первая приводит к ошибке. Найдите различие. Что произойдёт с аргументом в первом фрагменте? Какая команда во втором фрагменте прерывает цепочку вызовов?" | Сравнивают фрагменты, находят отсутствие базового случая в первой функции, формулируют: «Аргумент уменьшается, но функция никогда не возвращает результат без условия остановки». |
2 мин | Учитель фиксирует на доске три опорных понятия: "Базовый случай — условие остановки. Рекурсивный шаг — вызов функции с изменённым аргументом. Корректная рекурсия должна приближать аргумент к базовому случаю." Затем предлагает: "Сформулируйте цель урока одним предложением, используя глаголы «написать», «проверить» и «объяснить»." | Формулируют цель: «Написать простую рекурсивную функцию, проверить её на примерах и объяснить порядок вызовов». Записывают цель в тетрадь. |
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Запись в тетрадях
Рекурсия — способ организации алгоритма, при котором функция вызывает саму себя. Корректная рекурсивная функция содержит базовый случай и рекурсивный шаг. Каждый новый вызов должен приближать аргумент к базовому случаю.
Завершение этапа: учитель подводит итог: "Цель определена: не запомнить термин, а научиться писать и проверять работающий код. Переходим к открытию способа построения рекурсивной функции на конкретной задаче."
Этап 4. Открытие нового знания и практическое исследование (10 мин)
Цель этапа: на примере суммы чисел от 1 до $n$ вывести структуру рекурсивной функции и проследить последовательность вызовов.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель обращается к классу: "Рассмотрим задачу: найти сумму чисел от 1 до $n$. Для числа 1 ответ известен сразу: $1$. Для большего числа можно представить сумму так: $S(n)=n+S(n-1)$. Посмотрите на доску: здесь выделены базовый случай `n == 1` и рекурсивный шаг `n + summa(n - 1)`. Как изменяется параметр? Почему вызовы обязательно остановятся?" | Записывают зависимость $S(n)=n+S(n-1)$, называют базовый случай и объясняют: «Параметр уменьшается на единицу и в итоге станет равен 1». |
4 мин | Учитель набирает и запускает код: `def summa(n): if n == 1: return 1; return n + summa(n - 1)`. Затем говорит: "Не копируйте код механически. Сначала составьте трассировку для `summa(4)`: запишите вызовы сверху вниз, а возвращаемые значения — снизу вверх. После этого запустим программу и сравним результат." | В тетради строят цепочку: `summa(4) → 4 + summa(3) → 4 + 3 + summa(2) → 4 + 3 + 2 + summa(1)`. Затем записывают возврат: `1`, `3`, `6`, `10`; запускают код и проверяют результат. |
3 мин | Учитель предлагает исследование в парах: "Измените функцию так, чтобы она считала факториал числа $n$. Вспомните, что $n! = n \cdot (n-1)!$, а базовый случай можно задать для $n=1$. У вас три минуты. Если нужна поддержка, используйте подсказку: замените сложение на умножение. После запуска объясните партнёру, где находится каждый элемент рекурсии." | Создают функцию факториала, например `def fact(n): if n == 1: return 1; return n * fact(n - 1)`, проверяют значения `fact(3)` и `fact(5)`, называют базовый случай и рекурсивный шаг. |
Эталон решения
Для $fact(4)$: $fact(4)=4\cdot fact(3)$; $fact(3)=3\cdot fact(2)$; $fact(2)=2\cdot fact(1)$; $fact(1)=1$. Возврат выполняется в обратном направлении: $fact(2)=2$, $fact(3)=6$, $fact(4)=24$. Базовый случай прекращает дальнейшие вызовы.
Завершение этапа: учитель подводит итог: "Мы построили две функции по одной схеме: сначала указали простой случай, затем описали задачу через более простой вариант той же задачи. Теперь проверим понимание на коротких заданиях, где важно не только получить ответ, но и объяснить ход работы программы."
Этап 5. Первичное закрепление: трассировка и поиск ошибки (7 мин)
Цель этапа: закрепить умение читать рекурсивный код, строить цепочку вызовов и находить отсутствие условия завершения.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель раздаёт карточки базового уровня: `def g(n): if n == 0: return 0; print(n); return g(n - 1)`. Реплика: "Запустите функцию `g(3)` мысленно, не включая компьютер. Запишите, какие числа будут напечатаны и сколько раз функция вызовет саму себя. Затем проверьте ответ запуском." | Записывают последовательность `3, 2, 1`, определяют четыре вызова с учётом `g(0)`, запускают программу и сверяют результат. |
2 мин | Учитель показывает ошибочный код: `def h(n): if n == 0: return 0; return n + h(n + 1)`. Спрашивает: "Почему программа не завершится при положительном `n`? Предложите минимальное исправление. Не переписывайте функцию целиком: назовите строку и изменение." | Находят ошибку в направлении изменения аргумента, предлагают заменить `n + 1` на `n - 1`, объясняют, что аргумент должен приближаться к нулю. |
2 мин | Учитель организует взаимопроверку: "Обменяйтесь тетрадями. Поставьте две звезды за правильную цепочку вызовов и объяснение базового случая, а один совет запишите там, где не хватает проверки. После проверки верните работу автору и исправьте одну найденную неточность." | Проверяют работу по критериям, записывают две сильные стороны и один совет, исправляют ошибку в собственной трассировке. |
Завершение этапа: учитель подводит итог: "Теперь вы умеете читать готовую рекурсивную функцию и объяснять, почему она завершается. Следующий шаг — самостоятельное написание программы с выбором уровня сложности и обязательной проверкой граничных значений."
Этап 6. Самостоятельная практическая работа с дифференциацией и ИКТ (10 мин)
Цель этапа: применить алгоритм построения рекурсивной функции в самостоятельной работе с учётом индивидуального уровня подготовки.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель объясняет выбор заданий: "На карточках три уровня. Минимальный уровень — восстановить пропущенные строки в готовой функции и выполнить трассировку. Базовый уровень — написать функцию суммы цифр числа. Повышенный уровень — написать рекурсивную функцию подсчёта количества цифр в положительном числе и проверить её. Выберите уровень, который позволит вам работать самостоятельно, но потребует усилия." | Выбирают карточку, записывают номер уровня и проговаривают партнёру план: определить базовый случай, выбрать изменение аргумента, проверить результат. |
5 мин | Учитель консультирует по вопросам, не выдавая готовый код: "Проверьте, что будет происходить с аргументом после каждого вызова. Для суммы цифр используйте последнюю цифру `n % 10` и оставшуюся часть `n // 10`. Подумайте, какое значение имеет число, когда цифры закончились. Для подсчёта цифр протестируйте отдельно однозначное число." | Пишут и запускают программы. Минимальный уровень восстанавливает базовый случай и рекурсивный вызов; базовый решает задачу суммы цифр; повышенный решает задачу подсчёта цифр. Проверяют значения 0, 1, 7, 25 или 305 в зависимости от задания. |
3 мин | Учитель проводит самопроверку по листу: "Отметьте четыре пункта: базовый случай есть; аргумент меняется; вызов приближает к остановке; результат проверен вручную. Если хотя бы один пункт не отмечен, остановите запуск и исправьте код. Пара, закончившая раньше, сравнивает своё решение с циклическим алгоритмом и формулирует одно преимущество и одно ограничение рекурсии." | Заполняют лист самопроверки, исправляют код, фиксируют результаты тестов. Сильные учащиеся сравнивают рекурсивное решение с циклом и формулируют: «Рекурсия ближе к математическому описанию, но использует память стека и может быть менее эффективной». |
Эталон решения
Для суммы цифр: `def digit_sum(n): if n < 10: return n; return n % 10 + digit_sum(n // 10)`. Например, $digit\_sum(305)=5+digit\_sum(30)=5+0+digit\_sum(3)=8$. Для количества цифр: `def count_digits(n): if n < 10: return 1; return 1 + count_digits(n // 10)`. Для $305$: $1+count\_digits(30)=1+1+count\_digits(3)=3$.
Завершение этапа: учитель подводит итог: "Вы применили одну и ту же схему к разным задачам и увидели, что рекурсия требует особенно внимательной проверки аргумента. Сейчас кратко зафиксируем, что стало понятным, где осталось затруднение и какой вопрос возьмём с собой на следующий урок."
Этап 7. Рефлексия, подведение итогов и домашнее задание (6 мин)
Цель этапа: осознать способы построения рекурсивной функции, выявить затруднения и определить дальнейшую индивидуальную практику.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель предлагает приём «Одноминутная бумага»: "За одну минуту запишите два предложения: «Теперь я умею…» и «Мне нужно ещё потренироваться…». Не переписывайте определения, назовите конкретное действие с кодом. Затем прикрепите стикер на шкалу от 1 до 5: насколько уверенно вы можете объяснить базовый случай." | Записывают личный результат, прикрепляют стикер на шкалу понимания. |
2 мин | Учитель задаёт вопросы: "Что обязательно должно быть в рекурсивной функции? Почему изменение аргумента должно вести к базовому случаю? Какая ошибка вызывает бесконечные вызовы? В каких задачах рекурсивная запись может быть естественнее цикла?" | Отвечают: «Базовый случай и рекурсивный шаг»; «иначе функция не завершится»; «аргумент не меняется или удаляется от условия остановки»; приводят пример обработки вложенных структур или вычисления факториала. |
2 мин | Учитель объявляет домашнее задание: "Выберите обязательный уровень, а затем при желании добавьте повышающий или дополнительный. Перед сдачей проверьте каждую программу на граничном значении и приложите две строки объяснения: где базовый случай и как меняется аргумент." | Записывают выбранный уровень домашнего задания, задают уточняющие вопросы, закрывают программы и сдают листы саморефлексии. |
Завершение этапа: учитель подводит итог: "Сегодня вы научились видеть в рекурсии не магию, а точную структуру: базовый случай, рекурсивный шаг и движение к остановке. Проверьте дома не только правильный ответ, но и путь, которым программа к нему приходит. На следующем уроке рассмотрим рекурсивную обработку строк или последовательностей и обсудим эффективность рекурсивных решений."
Критерии оценивания практической работы
- «5» — самостоятельно выполнено задание выбранного уровня, в программе есть корректный базовый случай и рекурсивный шаг, выполнены минимум три осмысленных теста, включая граничное значение; ученик может объяснить порядок вызовов.
- «4» — программа решает основную задачу, но допущена одна неточность в оформлении, трассировке или выборе теста; после подсказки ученик самостоятельно исправляет ошибку.
- «3» — выполнена часть задания, базовый случай определён с помощью учителя, но объяснение рекурсивного шага или проверка граничного значения неполные.
- Ниже базового уровня — отсутствует работающий результат или не определено условие остановки; учащемуся предлагается повторно выполнить минимальное задание с опорной схемой.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что обязательно должно быть в рекурсивной функции и зачем? | Проверка осознания структуры рекурсивного алгоритма и роли базового случая. |
Как вы проверяли, что аргумент приближается к условию остановки? | Выявление понимания механизма завершения и профилактика бесконечной рекурсии. |
Какое место в практической работе оказалось самым сложным? | Выявление точек затруднения: проектирование, кодирование, трассировка или тестирование. |
Какой уровень задания вы выбрали и что позволило бы перейти на следующий? | Формирование адекватной самооценки и индивидуализация дальнейшей практики. |
Завершающее слово учителя
"Сегодня мы разобрали, как функция может вызывать саму себя и при этом завершаться. Главное условие — наличие базового случая и изменение аргумента в направлении этого случая. Типичная ошибка — написать рекурсивный вызов, но забыть проверить минимальное значение или изменить аргумент не в ту сторону. Дома обязательно протестируйте программы на граничных данных. На следующем уроке мы применим рекурсию к обработке более сложных структур."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Написать и протестировать две рекурсивные функции: вычисление суммы чисел от 1 до $n$ и факториала числа $n$. Для каждой привести по три теста, включая минимальное допустимое значение, и подписать базовый случай. | Закрепляет базовую структуру рекурсии; при проверке обратить внимание на остановку, изменение аргумента и совпадение результата с ручным вычислением. |
Средний (повышающий) | Написать рекурсивную функцию нахождения суммы цифр положительного числа и функцию определения количества цифр. Проверить каждую на однозначном, двузначном и трёхзначном числе; кратко сравнить с решением через цикл. | Формирует умение уменьшать задачу через операцию `n // 10`; при проверке смотреть на корректную обработку однозначного числа и отсутствие бесконечной рекурсии. |
Продвинутый (дополнительный) | Разработать рекурсивную функцию вычисления наибольшего общего делителя по алгоритму Евклида или функцию проверки, является ли строка палиндромом. Описать базовый случай, рекурсивный шаг и оценить, сколько вызовов выполняется на двух примерах. | Развивает исследовательское и алгоритмическое мышление; при проверке оценить обоснование выбора базового случая, корректность граничных тестов и ясность объяснения. |
Контрольные вопросы перед выходом: «Что такое базовый случай? Как понять, что рекурсивный вызов приближает нас к нему? Какая ошибка приводит к бесконечной рекурсии? Назовите одну задачу, которую сегодня вы решили рекурсивно».
