Методика изучения информатики с помощью рекурсивного метода.

Творческий подход к решению задач с использованием рекурсивных методов, установление причинно-следственной связи между подзадачами, историческая или мифологическая природа отдельных проблем (проблема Джозефа Флавия, проблема Ханойских башен для n = 64), построение рекурсивных объектов графически (рекурсивное дерево, снежинки Коха и Мандельброта, кривые Серпинского) - все это может развить интерес к обучению и стремление к самообразованию.Более эффективному обучению информатике во многом способствует математическая подготовка студентов [4]. Углубленное обучение математике формирует логическое и алгоритмическое мышление студентов, математические методы успешно применяются в моделировании. С другой стороны, информатика предоставляет комплекс компьютерных технологий, предназначенных для решения целых классов математических задач. Рекурсивные определения и алгоритмы также являются мощными инструментами в математике. Сила рекурсивного определения состоит в том, что оно позволяет определять бесконечное множество объектов с помощью конечного оператора [9].2.2. Методическиеразработки уроковпоизучениюосноврекурсииУрок «Рекурсия»Цель: дать учащимся представление о рекурсии и возможностях ее использования.Задачи:образовательная: сформировать понятия рекурсивного объекта и рекурсивного определения, познакомить учащихся с рекурсивными алгоритмами, научить ребят составлять программы с использованием рекурсивных функций; выражений на алгоритмический язык;развивающая: развивать логическое мышление;воспитательная: воспитывать интерес к предметуСтруктура урокаI. Организационный моментII. Актуализация знаний.III. Изучение нового материала.IV. Итог урока. Домашнее задание.Ход урокаI. Организационный моментII. Актуализация знанийКак описывается функция?Каковы отличия функции от процедуры?Чем отличаются друг от друга формальные и фактические параметры?Что такое область действия переменной?Чем отличаются друг от друга глобальные и локальные параметры?III. Изучение нового материалаПодпрограммыв TurboPascal и могут обращаться к самим себе. Такое обращение называется рекурсией. Объект, который частично определяется через самого себя, называется - рекурсивным. Рекурсивные определения как мощный аналитический аппарат используются во многих областях науки, особенно в математике. Для того, чтобы не было бесконечного обращения подпрограммы к самой себе, требуется наличие некоторого условия (условного оператора) в тексте программы, по достижении которого дальнейшее обращение не происходит. Таким образом, рекурсивное программирование может включаться только в одну из ветвей условного оператора, присутствующего в подпрограмме.Описаниепроцессовосуществляется спомощьюалгоритмов.2 этапавыполнения рекурсивныхалгоритмов:«Погружение» алгоритма всебя, т. е. применение определения "в обратную сторону", пока не будет найдено начальное определение, не являющееся рекурсивным;Последовательное построение отначальногоопределениядо определениясвведеннымв алгоритмзначением.Некоторые задачи являются рекурсивными по своему определению, поэтому рекурсивные алгоритмы – это точные копии с соответствующего определения.Пример 1.Классическийпример, безкоторого не обходятсяни в одномрассказе орекурсии, — определениефакториала. Содной стороны, факториал определяется так: n!=1·2·3·...·n. С другой стороны, Граничным условием в данном случае является n<=1.Для вычисления факториала опишем функцию, которая будет вычислять его значение. Ей будет передаваться целое число, поэтому у нее есть только один параметр. Результат выполнения - тоже целое число. Например, можно описать такую функцию:Functionfactorial (n: integer): longin t;beginif n=l thenfactorial: =1elsefactorial: =n·factorial (n-l);end.Найдем 3! Какже будет вычислятьсяфакториалэтого числа? Первый вызовэтой функции будетиз основной программы (Например, а:=factorial(3)), где переменной а присваиваем значение 3!). Надо заметить, что при каждом обращении к функции будет появляться свой набор локальных переменных со своими значениями, в данном случае - переменная n, для которых выделяется память. А после завершения работы эта часть памяти освобождается и переменные удаляются.Так какN<>1, то пойдем по ветке Else и функции Factorial присваиваем значение n*Factorial(n-l), то есть надо умножить 3 на значение функции Factorial(2). Поэтому обращаемся второй раз к этой же функции, но передаем ее новое значение параметра -2. Так делаем до тех пор, пока не передадим значение, равное 1. Тогда N=1, а поэтому значение функции Factorials 1. Таким образом, N=1 - это условие, по которому процесс входа в следующую рекурсию заканчивается. Идет возвращение в точку вызова и подстановка в оператор присвоения значения вычисленной функции. То есть возвращаемся в предыдущую функцию для N=2: Factorial:=n·Factorial(n-l), значит, Factorial:=2·l, следовательно, Factorial(2)=2. И возвращаемся дальше n=3: Factorialsn·Factorial(n-l), значит, Factorial – 3·2·1, следовательно, Factorial(3)=6.. Таким образом, получаем значение Factorial(3)=6, это значение и присвоим переменной а.usescrt;var п: integer; a.longint;functionfactorial (n: integer): longint;beginif n=l thenfactorial :=1elsefactorial :=n*factorial (n-'l);end;beginclrscr;writeln('n=');readln(n);a:=factorial (n);writeln('a=',a);readln;end.Пример 2.НахождениеНОД (наибольшего общего делителя) двух натуральных чисел.Решение.Естьнесколькоспособов нахождения этогозначения. Одним из нихявляется алгоритм Евклида. Рассмотрим еще один из вариантов его реализации.Пусть есть двацелых числаа и b.Еслиа=b, то НОД(а,b)=а.Еслиа>b, то НОД(а,b)=НОД(а-b,b).Еслиаb, то а = а-b616так как b>а, то b = b-а610b = b-а64так как а>b, то а =а-b24b=b-а22Так как а = b,то НОД=аТаким образом, можно составить следующую функцию и программу:uses crt;var a,b:longint;function nod (a,b:longint):longint;beginif a=b then nod: =a else if a>b then nod:=nod(a - b,b)else nod:=nod(a,b- a)end;beginclrscr;writeln('a-b=') ;readln(a, b);a:=nod(a,b);writeln('nod=’, a);readln;end.Пример 3.Перевод натурального числа из десятичной системы счисления в двоичную.Для решенияэтой задачи рассмотрим сначала, какперевести числоиз десятичной системысчисления вдвоичную. Пустьесть число 39, которое инадо представитьвдвоичной системе. Дляэтого разделим его на 2, получим целую часть и остаток от деления. Целую часть снова делим на 2 и получаем целую часть и остаток. Так делаем до тех пор, пока целую часть можно делить на 2 (то есть пока она не станет равной 1).Теперь, начинаясэтой единицы, выписываем в обратном порядке все остатки от деления, это и будет запись числа 39 в двоичной системе счисления: 3910=1001112.Таким образомможно переводить любоенатуральноечисло из десятичной системысчисления вдвоичную, атакжеидругие системы (например, восьмеричную или шестеричную).uses crt;var n.longint;procedure REC (n:longint);beginif n>l then rec(n div 2);writeln (mod 2);end;beginclrscr;writeln('n - ');readln(n);rec(n);readln;end.Результат на экране: 100111.Первая цифра (1) выводится на экран из последнего вызова, следующая цифра (0) - из предпоследнего и так далее, последняя (1) - из первого. Таким образом, вывод очередной цифры происходит перед тем, как выйти из данной функции.IV. Домашнее задание;Повторить понятие процедур и функций.Выучить конспект.Написать программу нахождения факториала числа при помощи рекурсивной функции.ЗаключениеВ настоящее время область практического применения рекурсии очень широка. Он включает в себя сложные задачи численного анализа, алгоритмы перевода и различные операции со списками. Поэтому аппарат рекурсии предусмотрен практически во всех языках программирования.Важность рекурсии определяется тем, что это один из самых мощных и наиболее общих методов научного познания. Он эффективно применяется во многих прикладных и теоретических дисциплинах естествознания и стал их неотъемлемой частью.На основании проделанной работы можно сделать несколько выводов:рекурсивные алгоритмы – универсальное средство решения различных алгоритмических задач. Любая решаемая задача такого рода имеет рекурсивное решение, которое в то же время отличается элегантностью и простотой для человеческого восприятия;рекурсивные алгоритмы часто имеют более низкуюасимптотическую сложность, чем их эквивалентные итерационные алгоритмы. То есть по идее они быстрее;развитие современных программных средств сделало практическое использование рекурсии довольно простым, а новые концепции и технологии программирования преодолели проблему низкой эффективности рекурсивных программ.Рекурсия отражает особенность абстрактного мышления, которая проявляется в самых разных приложениях в математике, синтаксическом анализе и переводе, сортировке дерева и обработке данных с динамической структурой, шахматных задачах и т. д. Именно в задачах такого рода лучше использовать рекурсивные алгоритмы, поскольку они исключают необходимость последовательного описания процессов, кроме того, практически все существующие языки программирования поддерживают рекурсию.Список литературыАрсак Ж. Программирование игр и головоломок. - М.: Наука, 1990Баррон Д. Рекурсивные методы в программировании. - М.: Мир, 1974.Бердж В. Методы рекурсивного программирования. М.: Машиностроение, 1983.Ваныкина Г.В. Изучение рекурсии как метод совершенствования информационной и математической культуры учащихся// Пединформатика, №2, 2004.Головешкин В.А., Ульянов М. В. Теория рекурсии для программистов. М.: ФИЗМАТЛИТ, 2006.Гремальский А. Информатика. Язык программирования Паскаль. 2001Добровольский Н. М., Есаян А. Р., Шулюпов В. А. О рекурсивных алгоритмах вычисления факториала // Труды IX Междунар. конф. "Информационные технологии в образовании - ИТО-99", - М.: Изд-во МИФИ, 1999.Елькина И. Э. Технология решения задач с использованием рекурсии // Тр. X конф. "Информационные технологии в образовании - ИТО-2000". - М.: МИФИ, 2000.Есаян А. Р. Обучение алгоритмизации на основе рекурсии: Учеб. пособие для студентов пед. вузов. - Тула: Изд-во ТГПУ им. Л. Н. Толстого, 2001.Есаян А. Р. Рекурсия информатике: Учеб. пособие для студентов пед. вузов: Ч. 1: Корзина разнообразных задач. - Тула: Изд-во ТГПУ им. Л. Н. Толстого, 2000.Информатика в уроках и задачах: приложение к журналу «Информатика и образование». № 3 - 1999. - М.: Информатика и образование, 1999.Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983.Мальцев А.И. Алгоритмы и рекурсивные функции. – М., 1965.Могилев А.В. И др. Информатика: Учебное пособие для студ. высш. учеб. заведений. – 2-е изд., стер. – М.: Изд. Центр «Академия», 2001.Могилев А.В. И др. Практикум по информатике: Учебное пособие для студ. пед. вузов. – 2-е изд., стер. – М.: Изд. Центр «Академия», 2001.