Кандидат педагогических наук, Хмара Е.В.

Студентка факультета математики и информатики, Табакова Т.С.

Славянский-на-Кубани государственный педагогический институт, Россия

Некоторые аспекты изучения рекурсии в школьном курсе информатики.

Модернизация современного школьного образования одним из направлений определила усиление общеобразовательной значимости естественно-научной подготовки школьников. Это повлекло за собой расширение и углубление вопросов государственного стандарта по информатике в классах физико-математического, информационно-технологического профилей. При этом в методике преподавания школьной информатики отмечается большое значение обучения учащихся основам алгоритмизации.

Довольно важными в теории алгоритмов и программировании, и в тоже время сложными темами школьного курса информатики является понятие рекурсии и связанное с ним построение рекурсивных алгоритмов. Поэтому оптимальным будет изучение этих вопросов в рамках факультативного или элективного курсов.

Введение рекурсивных алгоритмов и функций в школьный курс информатики обусловлено достаточным уровнем математической подготовки школьников (элементы функционального анализа, элементы комбинаторики), их возрастными особенностями и большим интересом к фундаментальным наукам, открытиям. Учащиеся, начиная со среднего звена школы, изучают различные математические функции. Многие из таких функций являются рекурсивными, вычислимыми. В связи с этим изучение рекурсивных алгоритмов и функций, по-нашему мнению, не должно вызывать сложностей у учащихся, а позволит расширить, углубить и систематизировать их знания, а также способствовать планомерному, поэтапному формированию алгоритмического стиля мышления.

Понятие рекурсии просто для начального понимания и не связано с какими-либо специальными знаниями, поэтому рекурсивные методы можно начинать рассматривать на примере решения задачи о Ханойских башнях. Однако для дальнейшего изучения рекурсии в рамках базового и профильного курсов необходимо формирование понятийно-терминологического аппарата, для чего потребуется изучение таких понятий, как рекурсивный алгоритм, прямая и косвенная рекурсия, рекурсивный стек, глубина рекурсивных вызовов, декомпозиция, управляющие параметры рекурсии, прямой и обратный ход вычислений, возвратная рекурсия и др. На данном этапе также потребуются знания учащихся в области алгоритмизации и структурного программирования.

Традиционными примерами рекурсивных алгоритмов являются задачи вычисления элементов последовательности Фибоначчи и факториала натурального числа, нахождения наибольшего общего делителя двух чисел, быстрой сортировки Хоара, бинарного поиска. При этом, некоторые алгоритмы естественно рекурсивны, и их гораздо проще понять в рекурсивном представлении.

На примере нахождения факториала и наибольшего общего делителя учащимся можно показать, что любая рекурсивная программа легко преобразуется в нерекурсивную, выполняющую те же вычисления. И наоборот, используя рекурсию, любое вычисление, предполагающее применение циклов, можно реализовать, не прибегая к циклам.

Высокая эффективность учебных занятий в рамках профильного обучения немыслима без организации самостоятельной познавательной деятельности учеников в течение всего урока и при подготовке домашних заданий. Творческий подход к решению задач рекурсивными способами, установление причинно-следственной связи между подзадачами, исторический или мифологический характер отдельных задач (задача Иосифа Флавия, задача о Ханойских башнях), построение рекурсивных объектов графическими средствами (рекурсивное дерево, снежинки Коха и Мандельброта, кривые Серпинского) - все это может развивать интерес к обучению и стремление к самообразованию. Привлечение геометрического материала подчеркивает многообразие моделей и методов работы с ними.

На предлагаемых примерах можно наглядно продемонстрировать изучение и закрепление основных понятий рекурсии. В качестве программно-методического средства реализации составленного алгоритма решения задачи при изучении рекурсии можно использовать язык программирования Turbo Pаscal или разработанную на его основе визуальную оболочку Delphi.

Оценка трудоемкости и эффективности рекурсивных алгоритмов средствами информатики позволяет ставить и решать задачу о поиске рациональных способов решения. Поэтому следует обратить внимание учащихся на три основные проблемы, возникающие при программировании рекурсии:

1. Бесконечная рекурсия. Любой рекурсивный алгоритм должен иметь надежное условие остановки. Можно создать рекурсивную функцию, которая никогда не возвращает результата и не достигает конечной точки, что вызывает бесконечный цикл.

2. Бесполезный расход памяти. При обработке сложной цепочки рекурсивных обращений программа может исчерпать всю память стека. Объявляя переменные глобально, можно сократить использование стека.

3. Неуместная рекурсия. Обычно это происходит, когда алгоритм много раз вычисляет одни и те же промежуточные значения. Этот процесс можно рассмотреть на примере чисел Фибоначчи. Для устранения проблем подобного рода можно переписать алгоритм методом «снизу вверх».

Тем не менее, использование рекурсии является красивым приёмом программирования, при изучении которого учащиеся смогут закрепить навыки формализованного описания поставленных задач, получить прочные знания по базовым понятиям, научиться составлять рекурсивные алгоритмы и использовать их при решении других задач. Однако, прибегая к рекурсии, надо понимать, какую выгоду можно от неё получить, и стремиться увеличить выгоду и сократить вклад отрицательных качеств рекурсии.