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

Программа на языке Паскаль: 

type

    st = (left, middle, right);

    nat = 1..maxint; 

 

var

    m: nat; {m – число дисков} 

 

procedure move(n: nat; s1, sw, sk: st);

{перемещение n дисков с s1 на sk}  

 

    procedure step;

    {перемещение одного диска с s1 на sk} 

 

        procedure print(s: st);

            begin

                case s of

                    left: write(' лев. ');

                    middle: write(' средн. ');

                    right: write(' прав. ')

                end;

            end; 

 

        begin {step}

            write(' снять диск с ');

            print(s1);

            write(' надеть на  ');

            print(sk);

            writeln

        end; 

 

    begin {move}

        if n = 1 then

            step

        else begin

            move(n - 1, s1, sk, sw);

            step;

            move(n-1, sw, s1, sk)

        end

    end; 

 

begin

    read(m); {число дисков}

    writeln('для ', m:3, ' дисков следует произвести ',

    'следующие действия:');

    move(m, left, middle, right); 

 

readln

end.

Рассмотрим  следующий  пример: пусть требуется написать программу, для построения такой фигуры, изображенной на рисунке.

Фигура представляет собой равнобедренный прямоугольный  треугольник с длиной катета равной a. Внутри него располагаются три равных треугольника (также прямоугольных и равнобедренных). Катеты внутренних треугольников в 2 раза меньше катетов внешнего. Каждый из внутренних треугольников также содержит внутри себя по три треугольника, которые в свою очередь могут содержать еще более маленькие треугольники и так далее.

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

Подпрограмма  для решения такой задачи может выглядеть, например, так:

procedure triangle(x,y,a:integer); {пусть (x,y) — положение прямого  угла, a — длина катета}

begin

line(x, y, x + a, y);

line(x, y, x, y - a);

line(x + a, y, x, y - a); {построили контур большого треугольника}

if (a>1) then begin {если  наш треугольник должен содержать  внутренние — построим их по  тому же правилу что и большой}

triangle(x, y, a div 2); {меньший  треугольник, у которого общий  с большим прямой угол}

triangle(x, y — a div 2, a div 2); {верхний треугольник}

triangle(x + a div 2, y, a div 2); {правый треугольник}

end;

end;

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

Кстати, на примере этого решения хорошо видно, что рекурсию не всегда легко заменить циклом.

Рассмотрим  еще один пример: пусть требуется написать подпрограмму для изображения серии вложенных окружностей. Окружность диаметра d содержит внутри себя 4 одинаковых окружности диаметра d/2, которые касаются ее в верхней, нижней, правой и левой точках. С свою очередь каждая из четырех внутренних окружностей также содержит внутри еще по 4 окружности меньшего диаметра и так далее.

Аналогично предыдущей задаче, любая из внутренних окружностей  есть полное подобие внешней. Окончание  рекурсивных вызовов будет задаваться условием d<=1 (на каком-то уровне упрощения  окружность превратилась в точку).

Подпрограмма  для решения этой задачи может выглядеть, например, так:

procedure circles(x,y, r : integer); {пусть (x,y) — координаты  центра окружности, r - радиус }

begin

circle(x,y,r);

if (r>=2) then begin

circles(x — r div 2, y, r div 2);

circles(x + r div 2, y, r div 2);

circles(x, y — r div 2, r div 2);

circles(x, y + r div 2, div 2);

end;

end;

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

Рассмотрим  применение рекурсивного алгоритма  в жизненной ситуации.

Моделирование работы автопарковки

Имеется автопарковка, на которую автомобили ставятся в один ряд. Длина автопарковки — N метров. Ширина автомобиля — x метров. К сожалению, на парковке отсутствует разметка — то есть каждый подъезжающий водитель находит произвольное (случайное) место, достаточное для размещения автомобиля и ставит туда свою машину. Если не осталось свободного места ширины достаточной ширины, то парковка считается заполненной. Требуется смоделировать данный процесс и определить, сколько автомобилей будет помещаться на парковке при полном заполнении (если процесс моделирования повторить несколько раз, то можно получить достаточно точную статистику и определить, сколько автомобилей в среднем будет находиться на этой стоянке).

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

На рисунке показано возможное размещение автомобилей.

Идея решения: представим всю парковку в виде отрезка числовой прямой от 0 до N. Тогда первый автомобиль поделит этот отрезок на две части — слева от автомобиля и справа. Каждый из полученных отрезков мы можем рассматривать независимо и заполнять по тем же правилам, что и основной.

Продемонстрируем  процесс моделирования на рисунках:

Начальная ситуация: Дана незанятая парковка

Первый этап. В произвольное (случайно выбранное) место поставлен  автомобиль. Пусть левая граница  автомобиля имеет координату a, тогда правая a+x.

Получилось два отрезка: [0; a] и [a+x; N], для каждого из которых  необходимо решить точно такую же задачу — разместить автомобили.

Подпрограмма  для решения этой задачи моделирования может выглядеть так:

function Cars(left, right : real) : integer;

var

place: real;

begin

if right-left<x then Cars:=0 {терминальное условие: на отрезок  недостаточной ширины машину  поставить нельзя}

else begin

place:=random*((right-x)-left) + left; { случайно выберем левую границу автомобиля}

Cars:=Cars(left, place) + Cars (place + x, right);

end;

end;

Стоит обратить внимание на формулу place:=random·((right-x)-left) + left. Здесь random — это функция, генерирующее случайное число в интервале [0; 1]. Левая граница автомобиля не может находиться ближе чем на расстоянии x от правого края парковки (иначе правая часть автомобиля окажется за пределами парковки), поэтому ширина дипазона случайных чисел (множитель при random) взята не (right-left), а ((right-x)-left). Внутренние скобки здесь носят логический, а не математический характер. Понятно также, что координата левой границы автомобиля не может быть меньше, чем левая граница отрезка. Отсюда последнее +left в формуле.

IV. Домашнее задание;

Напишите рекурсивную  программу построения фигуры.

 

 

Заключение

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

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

На основании проведенной  работы можно сделать несколько выводов:

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

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

 

Литература

1. Арсак Ж. Программирование игр и головоломок. - М.: Наука, 1990
2. Баррон Д. Рекурсивные методы в программировании. - М.: Мир, 1974.
3. Бердж В. Методы рекурсивного программирования. М.: Машиностроение, 1983.
4. Ваныкина Г.В. Изучение рекурсии как метод совершенствования информационной и математической культуры учащихся// Пединформатика, №2, 2004.
5. Головешкин В.А., Ульянов М. В. Теория рекурсии для программистов. М.: ФИЗМАТЛИТ, 2006.
6. Гремальский А. Информатика. Язык программирования Паскаль. 2001
7. Добровольский Н. М., Есаян А. Р., Шулюпов В. А. О рекурсивных алгоритмах вычисления факториала // Труды IX Междунар. конф. "Информационные технологии в образовании - ИТО-99", - М.: Изд-во МИФИ, 1999.
8. Елькина И. Э. Технология решения задач с использованием рекурсии // Тр. X конф. "Информационные технологии в образовании - ИТО-2000". - М.: МИФИ, 2000.
9. Есаян А. Р. Обучение алгоритмизации на основе рекурсии: Учеб. пособие для студентов пед. вузов. - Тула: Изд-во ТГПУ им. Л. Н. Толстого, 2001.
10. Есаян А. Р. Рекурсия информатике: Учеб. пособие для студентов пед. вузов: Ч. 1: Корзина разнообразных задач. - Тула: Изд-во ТГПУ им. Л. Н. Толстого, 2000.
11. Информатика в уроках и задачах: приложение к журналу «Информатика и образование». № 3 - 1999. - М.: Информатика и образование, 1999.
12. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. – М., 1983.
13. Мальцев А.И. Алгоритмы и рекурсивные функции. – М., 1965.
14. Могилев А.В. И др. Информатика: Учебное пособие для студ. высш. учеб. заведений. – 2-е изд., стер. – М.: Изд. Центр «Академия», 2001.
15. Могилев А.В. И др. Практикум по информатике: Учебное пособие для студ. пед. вузов. – 2-е изд., стер. – М.: Изд. Центр «Академия», 2001.