Методические аспекты преподавания основ рекурсии

Методические аспекты преподавания основ рекурсии

 

Содержание

 

 

Введение

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

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

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

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

Задачи могут быть сформулированы следующим образом:

1. Выявить роль рекурсии при обучении алгоритмизации в школьном курсе информатики.

2. Провести краткий анализ методов рекурсивного программирования в обучении решению прикладных задач.

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

4. Разработать рекурсивные алгоритмы решения задач, с которыми приходится сталкиваться учащимся при изучении информатики. Реализовать эти алгоритмы на языке программирования Turbo Pascal.

 

 

Глава 1. Теоретические  основы изучения рекурсии

1.1.Понятие рекурсии и ее виды

Рекурсия – метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи [7].

Другими словами, рекурсия – способ общего определения объекта  или действия через себя, с использованием ранее заданных частных определений. Рекурсия используется, когда можно  выделить само подобие задачи.

В программировании рекурсия — вызов функции (процедуры) из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A. Количество вложенных вызовов функции или процедуры называется глубиной рекурсии [5].

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

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

Рекурсивный алгоритм (процедура, функция):

• алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма;
• рекурсивная функция – одно из математических уточнений интуитивного понятия вычислимой функции.

Адаптивный рекурсивный  алгоритм – алгоритм, который благодаря  рекурсивности учитывает те или  иные индивидуальные характеристики решаемой задачи из области своего определения.

Базис рекурсии – это  предложение, определяющее некую начальную  ситуацию или ситуацию в момент прекращения. Как правило, в этом предложении  записывается некий простейший случай, при котором ответ получается сразу, даже без использования рекурсии.

Шаг рекурсии – это правило, в теле которого обязательно содержится, в качестве подцели, вызов определяемого предиката.

Подпрограмма – все, что находится внутри рекурсивной функции.

Основное правило рекурсии: до рекурсивного вызова должна стоять проверка на возврат из рекурсии.

Существуют  следующие виды рекурсии [9]:

• прямая рекурсия – непосредственный вызов алгоритма (функции, процедуры, метода) из текста самого метода.

В данном случае функция f ( ) вызывает саму себя.

void f() {

............

f();

............

}

• косвенная рекурсия.

При косвенной рекурсии имеется циклическая последовательность вызовов нескольких алгоритмов.

Например, схема может  быть такой:

Рис. 1. Косвенная  рекурсия

Как видим, в main() вызывается функция A(), которая вызывает B(), а та в свою очередь вызывает снова A(). Понятно, что цепочка подпрограмм между вызовами функции A() могла быть не из одной функции B(), а из большего количества разных функции.

• линейная рекурсия – если исполнение подпрограммы приводит только к одному вызову этой же самой подпрограммы, то такая рекурсия называется линейной.

 

   

Рис. 2. Линейная рекурсия

Приведем пример вычисления факториала:

}

// Линейно-рекурсивный алгоритм

int fact(int n)

{

if (n==1) return 1;

return n * fact(n-1);

}

• ветвящаяся рекурсия – если каждый экземпляр подпрограммы может вызвать себя несколько раз, то рекурсия называется нелинейной или "ветвящейся".

Рис. 3. Ветвящаяся рекурсия

}

// Циклический алгоритм вычисления факториала

int fact(int n)

{

for (int s=1; n!=0; n--) s *=n;

return s;

• бесконечная рекурсия (на самом деле это условное обозначение так как при переполнении памяти компьютера программа выдаст ошибку и/или завершит ее в аварийном режиме).

Одна из самых больших  опасностей рекурсии – бесконечный вызов функцией самой себя.

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

function BadFactoriaKnum : Integer) : Integer;

begin

BadFactorial := num*BadFactorial(num-1);

end;

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

Имеется специальный  тип рекурсии, называемый «хвостовой рекурсией».[2] Интерпретаторы и компиляторы функциональных языков программирования, поддерживающие оптимизацию кода (исходного и/или исполняемого), автоматически преобразуют хвостовую рекурсию к итерации, благодаря чему обеспечивают выполнение алгоритмов с хвостовой рекурсией в ограниченном объёме памяти. Такие рекурсивные вычисления, даже если они формально бесконечны (например, когда с помощью рекурсии организуется работа командного интерпретатора, принимающего команды пользователя), никогда не приводят к исчерпанию памяти.

Нужно учитывать одну особенность, характерную для рекурсивных  программ, подобных той, которую используют для генерации чисел Фибоначчи.[6] Каждый уровень рекурсии в функции fibonacci удваивает количество вызовов, так что количество рекурсивных вызовов, которое должно быть выполнено для вычисления n – го числа Фибоначчи, оказывается порядка 2^N.

Объем вычислений резко  нарастает с увеличением n. Вычисление только 20 – го числа Фибоначчи  потребовало бы порядка 2^N или около миллиона вызовов, вычисление 30 – го числа Фибоначчи потребовало бы порядка 3^N или около миллиарда вызовов и так далее. В методах вычислений это называется экспоненциальной сложностью.

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

Любые задачи, которые  можно решить рекурсивно, могут быть решены также и итеративно (не рекурсивно). Обычно рекурсивный подход предпочитают итеративному, если он более естественно  отражает задачу и ее результаты, то есть более нагляден и легче отлаживается. Другая причина предпочтения рекурсивного решения состоит в том, что итеративное решение может не быть очевидным.[10]

Рекурсивные алгоритмы  в программировании реализованы  в механизме так называемых рекурсивных  подпрограмм. Рекурсивной считается подпрограмма, которая прямо или косвенно, через другие подпрограммы, обращается к себе, быть может с иными фактическими параметрами. В современных системах программирования корректное функционирование подпрограмм, особенно рекурсивных, обеспечивается с помощью стека. [13]

Стек – связная  структура данных, построенная на принципе «первый пришёл – первый вышел» (Fiгst In – Fiгst Out, FIFO). То есть вновь  добавляемые объекты помещаются в начало, вершину стека, и выбираются они также только из вершины. [13]

Стек является чрезвычайно удобной структурой данных для многих задач вычислительной техники. Наиболее типичной из таких задач является обеспечение вложенных вызовов процедур. Предположим, имеется процедура A, которая вызывает процедуру B, а та в свою очередь – процедуру C. Когда выполнение процедуры A дойдет до вызова B, процедура A приостанавливается и управление передается на входную точку процедуры B. Когда B доходит до вызова C, B приостанавливается и управление передается на процедуру C. Когда заканчивается выполнение процедуры C, управление должно быть возвращено в B, причем в точку, следующую за вызовом C.

При завершении B управление должно возвращаться в A, в точку, следующую  за вызовом B. Правильную последовательность возвратов легко обеспечить, если при каждом вызове процедуры записывать адрес возврата в стек. Так, когда процедура A вызывает процедуру B, в стек заносится адрес возврата в A; когда B вызывает C, в стек заносится адрес возврата в B. Когда C заканчивается, адрес возврата выбирается из вершины стека – а это адрес возврата в B. Когда заканчивается B, в вершине стека находится адрес возврата в A, и возврат из B произойдет в A.

Механизм вызова функции  или процедуры в языке высокого уровня существенно зависит от архитектуры  компьютера и операционной системы.[12] В рамках IBM PC совместимых компьютеров, в микропроцессорах семейства Intel, как и в большинстве современных процессорных архитектур, поддерживается аппаратный стек.

Аппаратный стек расположен в ОЗУ, указатель стека содержится в паре специальных регистров SS:SP доступных для программиста. Аппаратный стек расширяется в сторону уменьшения адресов, указатель его адресует первый свободный элемент. Схематично этот механизм иллюстрирован на рисунке 4. [2]

 

Рис. 4. Механизм вызова функции в аппаратном стеке

Языки PASCAL, C, C++ используют стек для размещения в нем локальных  переменных процедур и иных программных  блоков.[6] Стек разбит на фрагменты, представляющие собой блоки последовательных ячеек. Каждый вызов подпрограммы использует фрагмент стека, длина которого зависит от вызывающей подпрограммы. При каждой активизации процедуры память для ее локальных переменных выделяется в стеке; при завершении процедуры эта память освобождается. Поскольку при вызовах процедур всегда строго соблюдается вложенность, то в вершине стека всегда находится память, содержащая локальные переменные активной в данный момент процедуры.