Основные сведения. Методические указания по выполнению

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

ЛАБОРАТОРНОЙ РАБОТЫ № 12

По дисциплине: ОСНОВЫ ПРОГРАММИРОВАНИЯ

Наименование работы Исследование рекурсивных алгоритмов

Для специальности 230115 Программирование в компьютерных системах

Работа рассчитана на 2 часа

Разработал преподаватель

______________ В.М.Бакина

«12» 01 2013 г.

Цель работы: Научиться работать с рекурсивными алгоритмами.

Основные сведения

Сущность рекурсии

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

Рассмотрим, что произойдет, если в основной программе поставить вызов, например, вида Rec(3). Ниже представлена блок-схема, показывающая последовательность выполнения операторов.

Рис. 1. Блок схема работы рекурсивной процедуры.

Sub rec (n)

If n > 0 Then

Text1.Text = Text1.Text + Str(n)

n = n - 1

Call rec (n)

End If

End Sub

Private Sub Command1_Click()

n = Combo1

Call rec(n)

End Sub

Private Sub Command2_Click()

End

End Sub

Private Sub Form_Load()

Combo1.AddItem "2"

Combo1.AddItem "3"

Combo1.AddItem "4"

Combo1.AddItem "5"

Combo1.AddItem "6"

End Sub

Рис.2 Результат выполнения программы при n=3

Процедура Rec вызывается с параметром n = 3. В ней содержится вызов процедуры Rec с параметром n = 2. Предыдущий вызов еще не завершился, поэтому можете представить себе, что создается еще одна процедура и до окончания ее работы первая свою работу не заканчивает. Процесс вызова заканчивается, когда параметр n = 0. В этот момент одновременно выполняются 4 экземпляра процедуры. Количество одновременно выполняемых процедур называют глубиной рекурсии.

Четвертая вызванная процедура (Rec(0)) закончит свою работу. После этого управление возвращается к процедуре, которая ее вызвала (Rec(1)) и печатается число 1. И так далее пока не завершатся все процедуры. Результатом исходного вызова будет печать четырех чисел:

3, 2, 1

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

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

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

Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.

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

Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.

Основной задачей исследования рекурсивно заданных функций является получение f(n) в явной или как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:

Примеры рекурсивного задания функций

1. f(0)=0

f(n)= f(n-1)+1

2. f(0)=1

f(n)= n*f(n-1)

Последовательная подстановка дает – f(n)=1*2*3*…*n = n!

Формула Стирлинга для приближенного вычисления факториала для больших n:

3. f(0)=1

f(1)=1

f(n)= f(n-1)+ f(n-2), n>=2

Числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически

4. f(0)=1

f(n)= f(n-1)+ f(n-2)+…+1 = +1

Перевод чисел в 2 с/с: 51₁₀= 110011₂,деление на 2 осуществляется по рекурсивному алгоритму 51:2=25(1), 25:2=12(1); 12:2=6(0) пока результат не станет меньше основания т.е. 2.