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

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

 

Глава 2. Методика изучения основ рекурсии на уроках информатики

2.1. Методические рекомендации по  изучению основ рекурсии

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

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

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

• Рекурсия. А. Введение в определение объекта ссылки на сам объект. B. Прием сведения решения некоторой задачи к решению серии задач, подобных исходной. С. Свойство алгоритмической системы на промежуточных этапах своего функционирования создавать другие системы, включая идентичные себе самой, и использовать результаты их функционирования в дальнейшей работе. При достаточно широкой трактовке понятия алгоритмической системы концепция рекурсивности отражает основные формы развития материи и является одним из важнейших методов познания. D. Результат отчуждения (отвлечения, абстрагирования) свойств рекурсивности от совокупности рекурсивных объектов.
• Рекурсивный алгоритм (процедура, функция). A. Алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма. B. Рекурсивная функция — одно из математических уточнений интуитивного понятия вычислимой функции.
• Рекурсивные вычисления. Вычисления, проводимые с помощью рекурсивных алгоритмов (процедур, функций).
• Прямая рекурсия. Непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F.
• Косвенная (взаимная) рекурсия. Циклическая последовательность вызовов нескольких алгоритмов F-i, F₂, F_k (функций, процедур) друг друга: F-i вызывает F₂, F₂ вызывает F₃,     F_k вызывает F₁ (k>1).
• Рекурсивные обращения. Рекурсивные вызовы в прямой или косвенной рекурсии.
• Рекурсивная база. Совокупность наборов значений параметров и соответствующих им решений задачи или простых правил для получения этих решений. Выделение базы - один из основных этапов решения задачи с помощью рекурсии. База может быть динамической, то есть меняться в процессе вычислений.
• Рекурсивный стек. Область памяти, в которую заносятся значения всех локальных переменных алгоритма (программы) в момент рекурсивного обращения. Каждое такое обращение формирует один слой данных стека. При завершении вычислений по конкретному обращению а из стека считывается соответствующий ему слой данных, и локальные переменные восстанавливаются, снова принимая значения, которые они имели в момент обращения а.
• Глубина рекурсивных вызовов. Максимальное количество слоев рекурсивного стека, заполняемых при конкретном вычислении значения рекурсивной функции (процедуры, алгоритма). Количество элементов полной рекурсивной траектории всегда не меньше глубины рекурсивных вызовов. Эта величина не должна превосходить максимального размера стека используемой вычислительной среды. В то же время объём рекурсии - это характеристика сложности рекурсивных вычислений для конкретного набора параметров.
• Декомпозиция. Процесс последовательного разложения задачи на серию подзадач двух типов: тех, которые мы решать умеем и тех, которые в чем-то аналогичны исходной задаче. В последнем случае каждая из полученных подзадач должна быть упрощенным вариантом предыдущей задачи. При этом декомпозицию следует осуществлять так, чтобы можно было доказать, что при любом допустимом наборе значений параметров рано или поздно она приведет нас к одному из выделенных тривиальных случаев, то есть к задаче с набором параметров, являющимся индикатором завершения рекурсивных вызовов.
• Параметризация задачи. Выявление совокупности исходных величин, определяющих постановку и решение задачи. Значения этих параметров или некоторых из них влияют на трудоемкость решения задачи.
• Вспомогательные параметры рекурсии. Искусственно вводимые параметры, напрямую с постановкой задачи не связанные, но помогающие изменить тип рекурсии или перейти к обобщенной задаче, где рекурсия проглядывается явно.
• Рекурсивная триада. Три основных этапа решения задач с помощью рекурсии: параметризация, выделение базы (или выделение начальной базы и правил её изменения), декомпозиция.
• Предвычисления (предварительные вычисления). Декомпозиция предполагает наличие некоторых вычислений, предшествующих и способствующих переходам к более простым подзадачам. Их называют предварительными вычислениями или предвычислениями. Именно предвычисления и подготавливают переходы к следующим уровням рекурсивных обращений.
• Отложенные вычисления. Вычисления, проводимые после того, как рекурсивная траектория попала в базу, то есть стала полной. Возможно, что отложенные вычисления состоят лишь из серии передач значений и управления в порядке, обратном рекурсивным вызовам. В этом случае говорят об отсутствии отложенных вычислений.
• Управляющие параметры рекурсии. Один или несколько параметров задачи, с помощью которых организуется её декомпозиция и обеспечиваются правила выполнения рекурсивных вызовов. Значения управляющих параметров рекурсии могут участвовать в предварительных и отложенных вычислениях.
• Прямой и обратный ход вычислений. Рекурсивные вычисления состоят из двух стадий, называемых прямым ходом и обратным ходом. Первая из них соответствует совокупности всех предвычислений, реализуемых до входа рекурсивной траектории в базу, а вторая - совокупности отложенных вычислений, производимых после встречи с индикатором завершения рекурсивных вызовов.
• Возвратная рекурсия. Рекурсивная реализация метода перебора с возвратом.
• Динамическая рекурсивная база. Рекурсивная база, меняющаяся в процессе вычислений. Как правило, она расширяется за счет получения решений промежуточных задач и облегчает выполнение процесса отложенных вычислений. Возможно и сужение рекурсивной базы. Альтернативой динамической базы могут быть организуемые и поддерживаемые в процессе вычислений специальные списки решений промежуточных задач (динамическое программирование).
• Рекуррентное соотношение (рекуррентная формула). Формула вида a_n+_p = F(a_n, a„₊₁, a_n+_p-1) (p>1, n=1, 2, ...), позволяющая вычислять любой член бесконечной последовательности a₁, a₂, если заданы её первые p членов. Определяемая рекуррентной формулой последовательность называется возвратной. Прямая реализация рекурсивных вычислений по рекуррентным формулам неизбежно приводит к каскадной рекурсии. Однако во многих важных случаях от каскадной рекурсии удается избавиться. Рекуррентные соотношения часто используются для оценки рекурсивных алгоритмов.

Оценка трудоемкости и эффективности рекурсивных алгоритмов средствами информатики позволяет ставить и решать задачу о поиске рациональных способов решения (следует отметить, что данное понятие зависит от требований к реализации алгоритма).[4] Традиционным примером неэффективного использования рекурсии является задача о вычислении элементов последовательности Фибоначчи, однако, при использовании динамической базы рекурсии трудоемкость алгоритма значительно снижается.

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

Более эффективному обучению информатике во многом способствует математическая подготовка учащихся [4]. Углубленное обучение математике формирует логическое и алгоритмическое мышление учеников, математические методы успешно применяются в моделировании. С другой стороны, информатика предоставляет комплекс компьютерных технологий, предназначенных для решения целых классов математических задач. Рекурсивные определения и алгоритмы представляют собой мощный аппарат и в математике. Мощность рекурсивного определения заключается в том, что оно позволяет с помощью конечного высказывания определить бесконечное множество объектов [9].

• Натуральные числа:

а) 1 есть натуральное число,

б) число, следующее за натуральным, есть натуральное число.

 

• Факториал неотрицательного целого числа:

а) 0!=1,

б) n>0; n! = n(n-1)!

• Моделирование арифметических операций (сумма первых n натуральных чисел):

а) Si = 1,

б) n>1; S_n = S_n-1 + n.

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

• Вычисление биномиальных коэффициентов .

При   нахождении   биномиальных   коэффициентов   за   основу   принимается определение: или рассматриваются элементы треугольника Паскаля. Очевидно, что при больших n и m применение формулы непосредственно требует значительных вычислительных затрат (не  говоря уже о построении треугольника Паскаля). Например, . И если учащиеся затрудняются преобразовать дробь посредством сокращения (или неверно сокращают), то правильный конечный ответ не достигается. В реализации данного алгоритма средствами Turbo-Pascal при вычислении факториалов чисел происходит выход за разрядную сетку   типа Longint уже при n = 20. Если же предложить к рассмотрению зависимость между и через отношение

то может быть оформлена следующая рекурсивная зависимость:

а) ,

б) .

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

Function Binom (n,m : integer): Longint; Begin

if m = 0 then Binom := 1

     else Binom := n * Binom (n-1, m-1) div m;

End;

•   Нахождение наибольшего общего делителя (НОД) двух натуральных чисел с помощью алгоритма Евклида

Профильный курс математики предполагает изучение алгоритма Евклида в 8 классе, тогда как в обязательный минимум по математике данная тема не входит [4]. Прикладное же значение алгоритм Евклида получает при решении целых классов задач по информатике.

Пусть для определенности n > m и, по теореме о делении с остатком, Тогда имеет место рекурсивная зависимость:

а) если r = 0, то НОД (n, m) = m,

б) НОД (n, m) = НОД (m, r).

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

Function Evklid_2 (n,m : integer): integer;

   Var k: integer;

Begin

     if m > n then

        begin

k := m;

m := n;

n := k;

       end;

k := n mod m;

 if k = 0 then Evklid_2 := m

      else Evklid_2 := Evklid_2 (m, k);

End;

•   Нахождение наибольшего общего делителя (НОД) n натуральных чисел

При проведении параметризации задачи учащимся целесообразно предложить провести исследование с целью нахождения НОД для 3, 4,.., n чисел и математически доказать полученный результат, а также обосновать выделение базы рекурсии и декомпозиции:

а) НОД (а1, а2)

б) НОД (а1, а2,..., аn) = НОД (НОД (а_ъ а2,..., аn-1), аn)

Пусть для определенности объявлен массивовый тип и глобальная переменная этого типа:

 

Const min = 1;

max = 20;

Type dim = array [min..max] of integer;

Var t: dim;

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

Function Evklid_n (tab: dim; mi, ma: integer): integer;

Begin

if ma - mi = 1 then Evklid_n := Evklid_2 (tab[mi], tab[ma])

     else Evklid_n := Evklid_n (tab, mi, ma - 1);

End;

•   Перевод целых чисел из десятичной системы в систему счисления с основанием р

Профильный курс математики 9 класса предполагает знакомство учащихся с системами счисления и решение задач о переводе целых чисел между системами счисления с различными основаниями [8]. Пусть требуется перевести целое число m из десятичной в p-ичную систему счисления (для определенности ), то есть найти такое k, чтобы выполнялось равенство m₁₀ = k_p Результат математического моделирования задачи можно оформить в виде рекурсивной зависимости: а) если целая часть частного m и p равна нулю, то k = m,

б) k формируется из цифр целой части частного m и р, представленной в системе счисления с основанием р, и остатка от деления m на p.

Пусть в теле основной программы объявлена и определена глобальная строковая переменная alf := '0123456789ABCDEF'.

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

Function System_p (m, p: integer): string;

Var mod_m, div_m: integer;

Begin

div_m := m div p;

if div_m = 0 then System_p := alf [m+1]

   else begin

mod_m := m mod p;

 System_p := System_p (div_m, p) + alf [mod_m+1];

end;

End;

 

•    Перевод целых чисел из десятичной в Фибоначчиеву систему счисления

Стандартными в курсе информатики являются задачи о переводе чисел между системами счисления с постоянными основаниями [9]. Однако ряд прикладных задач оперирует системами счисления с переменным основанием, которое меняется по закономерности. Пусть требуется перевести целое число из десятичной системы счисления в такую, основание которой при переходе к старшему разряду изменяется в соответствии с рядом Фибоначчи: 1, 2, 3, 5, 8,... Алфавитом такой системы счисления являются два символа: 0 и 1, причем в записи числа символ 1 не может стоять в соседних разрядах, поскольку заполнение (k - 1)-го и k-го разрядов равносильно заполнению разряда (k + 1).

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

Пусть для определенности объявлен массивовый тип и необходимые глобальные переменные.

Const min = 1;

max = 20;

Type dim_fib = array [min-1..max] of longint;

Var f: dim_fib;

ind: min-1..max;

Dig : longint;  {десятичная запись переводимого числа}

Function Fib (n: integer): longint;

Begin

if ind < n then

     begin

 if n = 1 then f[n] := 1

     else f[n] := Fib(n - 2) + Fib(n - 1); ind := n;

end;

Fib := f[n];

End;

Пусть в теле основной программы объявлена и определена глобальная строковая переменная Raz := '10000000000000000000', соответствующая двадцатизнаковой разрядной единице системы Фибоначчи и найдено фактическое значение параметра index, равное порядковому номеру ближайшего элемента последовательности, не превосходящего данного числа Dig.

Рекурсивная функция System_fib обобщает понятия прямой и косвенной рекурсии, так как содержит обращения к самой себе, а также к ранее рассмотренной функции Fib.

Function System_fib (n, index: integer): string;

Begin

if Fib (index) = n then System_fib := Copy (Raz, 1, index)

if Fib (index) > n then System_fib := '0' + System_fib (n, index-1)