Элективный курс для учащихся 10-11 классов «Рекурсивные алгоритмы»

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

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

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

Основные понятия, связанные с рекурсией: глубина рекурсии, терминальное условие, прямой и обратный ход, стек.  Типичные примеры процедур и функций, использующих рекурсию, которые показывают школьникам: перевод чисел в двоичную систему счисления, нахождение n-го члена прогрессии, вычисление факториала, вычисление чисел Фибоначчи, нахождение НОД (алгоритм Евклида), возведение в степень, вывод массива без использования цикла, алгоритм быстрой сортировки, задача о Ханойской башне, построение фракталов. Интересны олимпиадные задачи.

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

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