Рекурсивные методы программирования. Рекурсивные подпрограммы

Дата:

Тема урока: Рекурсивные методы программирования. Рекурсивные подпрограммы.

Цели урока:

Образовательные (обучающие): познакомить учащихся с понятием рекурсия, рекурсивный алгоритм, разобрать примеры применения рекурсивных алгоритмов.

Развивающие: продолжить развивать навыки     владения ИКТ – технологией, логическое мышление, навыки работы с ЯП Pascal.

Воспитательные: способствовать воспитанию интереса к своей будущей профессии, проявлению  к ней устойчивого интереса (ОК 1 – общая компетенция).

Оборудование: ПО, презентация, учебник «Информатика и ИКТ» 11класс: Семакин И.Г.

Тип урока: урок изучения нового материала.

Ход урока

I. Организационный момент.

II. Сообщение темы и постановка цели урока

III. Изучение нового материала.

В параграфе 2.2.7 было введено понятие рекуррентной последовательности на примере следующего числового ряда:

[pic 1]

Было показано, что вычисление элементов этого ряда можно производить по формуле:

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

Будем рассматривать ап в качестве значений функции F(n) от целого аргумента п. Определение этой функции будет выглядеть так:

[pic 3]

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

Рекурсивные подпрограммы - функции и процедуры

В описаниях подпрограмм-функций на Паскале допускается использование в теле функции вызова этой же самой функции. Такая подпрограмма-функция называется рекурсивной.

Пример 1

Вот два варианта подпрограммы-функции вычисления F(n) = 1/n!

[pic 4]

Первый, нерекурсивный вариант подпрограммы имеет циклическую структуру. Во втором, рекурсивном варианте используется ветвление. На положительной ветви (then) значение функции вычисляется явно (FN:=1), на отрицательной ветви (else) происходит обращение функции к себе самой с уменьшенным на единицу значением аргумента.

Пусть в основной программе для вычисления 1/3! Имеется следующий оператор присваивания: P:=FN(3). При его выполнении произойдет цепочка обращений к рекурсивной функции FN с последующим возвратом:

[pic 5]

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

Вычисление частично-рекурсивной функции может быть реализовано также и в форме рекурсивно определенной процедуры. Ниже показан пример программы, в которой описана рекурсивная процедура вычисления 1 /п!. С помощью этой процедуры вычисляется значение 1/5!.

[pic 6]

В результате выполнения программы получено число:

0.008333333333.

Пример 2

Вспомним задачу вычисления наибольшего общего делителя двух чисел, описанную в параграфе 2.2.8. Задача решается с помощью алгоритма Евклида. Модифицированный алгоритм Евклида основан на следующей системе равенств: