Архив статей журнала
Одной из наиболее сложных тем школьного курса алгоритмизации и программирования является рекурсия. Использование среды графического исполнителя (ГРИС) позволяет сформировать у школьников ментальную алгоритмическую схему принципов построения и работы рекурсивных программ, которая упростит восприятие более сложных аспектов этой темы на дальнейших этапах обучения.
Не выходя за рамки ограниченных возможностей среды ГРИС, на простых наглядных примерах объясняются следующие понятия: рекурсивный вызов процедуры, отложенный возврат из процедуры, условие продолжения рекурсии, прямой и обратный шаги рекурсии. Показывается, как с помощью рекурсии могут быть реализованы цикл ПОКА и цикл ДО.
На примере нестандартной задачи рисования квадрата демонстрируется, как введение рекурсии приводит к сокращению размера программы и времени ее выполнения. Приводятся примеры задач для графического исполнителя, решения которых могут быть построены только с использованием рекурсии. Показывается, как рекурсия расширяет возможности позиционирования графического исполнителя.
Для проведения учебных занятий предлагается использовать независимую от вычислительной платформы реализацию ГРИС «Букашка», которая полностью совместима с ГРИС «Кенгурёнок РУ» и может быть интегрирована в информационную среду образовательной организации.
В статье представлен подход к изучению рекурсивных функций на углубленном уровне освоения курса информатики в X—XI классах на примере функций вычисления факториала и обобщенных функций Фибоначчи различного порядка. Являясь объектом исследования в рассматриваемой в статье исследовательской работе, эти функции предоставляют усредненные экспериментальные данные времени выполнения, которые в дальнейшем визуализируются, анализируются и аппроксимируются. В процессе такого анализа соотносятся теоретические оценки вычислительной сложности и полученные экспериментальные данные времени выполнения рекурсивных функций в зависимости от переменных аргументов. Показаны примеры двумерной визуализации времени выполнения функции вычисления факториала средствами языка программирования Python и трехмерной визуализации времени выполнения обобщенных функций Фибоначчи различного порядка в редакторе электронных таблиц. Выделены развиваемые STEM-компетенции, изучаемые теории, методы, принципы и концепции в науке, технологиях, инженерии и математике. Объектами научной новизны в данной работе являются: демонстрация нелинейной вычислительной сложности рекурсивного алгоритма вычисления факториала в Python при больших аргументах и выявление причин такого поведения данного алгоритма, основанное на контрпримере; написание рекурсивной обобщенной функции вычисления чисел рядов Фибоначчи с различным порядком как пример реализации принципа DRY; предложенные подходы к углубленному изучению рекурсии и знакомству обучающихся с теорией вычислительной сложности.
Рекурсивная функция для решения задания 23 ЕГЭ по информатике на динамическое программирование используется экзаменуемыми без глубокого понимания принципов ее работы: при сформированном навыке ее использования отсутствуют необходимые знания, что является беззнаниевой формой компетенции. Формирование понимания принципов работы программного кода и переход от беззнаниевой формы к полноценным компетенциям и компетентностям — информационным, цифровым, математическим, а также в области программирования — позволит ученикам получить более глубокие знания теории рекурсивных функций, сформировать навыки, деятельностные и ценностные отношения в области решения задач динамического программирования на более высоком уровне, что способно привести к улучшению образовательных результатов, пониманию методов динамического программирования, применяемых в том числе на ЕГЭ и олимпиадах по информатике. Для формирования знаниевой компоненты компетенции предлагается построение, изучение и использование деревьев вызовов рассматриваемой рекурсивной функции, созданных в среде программирования Observable, а также изучение мемоизации как ключевого отличия метода динамического программирования от рекурсии.