«Рекурсивные функции и алгоритмы. рекурсивные алгоритмы и методы их анализа»

  • 31 мая 2013 г.
  • 1581 Слова
ГОСУДАРСТВЕННОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«БЕЛОРУССКО-РОССИЙСКИЙ УНИВЕРСИТЕТ»

Кафедра «Автоматизированные системы управления»





Реферат на тему:
«РЕКУРСИВНЫЕ ФУНКЦИИ И АЛГОРИТМЫ. РЕКУРСИВНЫЕ АЛГОРИТМЫ И МЕТОДЫ ИХ АНАЛИЗА»
по дисциплине
«Математическая логика и теория алгоритмов»







Выполнил: ______________
Проверил: ______________Могилев, 2010

СОДЕРЖАНИЕ

1 Рекурсивные функции
2 Рекурсивная реализация алгоритмов
3 Анализ трудоемкости механизма вызова процедуры
4 Анализ трудоемкости алгоритма вычисления факториала
5 Логарифмические тождества
6 Методы решения рекурсивных соотношений
7 Рекурсивные алгоритмы
8 Основная теорема о рекуррентных соотношениях


1 РЕКУРСИВНЫЕ ФУНКЦИИ

а) Терминологическое введение. Посути один и тот же метод, применительно к различным областям носит различные названия – это индукция, рекурсия и рекуррентные соотношения – различия касаются особенностей использования.
Под индукцией понимается метод доказательства утверждений, который строится на базе индукции при n=0,1, затем утверждение полагается правильным при n=n b и проводится доказательство для n+1.
Под рекурсиейпонимается метод определения функции через её предыдущие и ранее определенные значения, а так же способ организации вычислений, при котором функция вызывает сама себя с другим аргументом.
Термин рекуррентные соотношения связан с американским научным стилем и определяет математическое задание функции с помощью рекурсии.
Основной задачей исследования рекурсивно заданных функций является получение (n) в явнойили как еще говорят «замкнутой» форме, т.е. в виде аналитически заданной функции. В связи с этим рассмотрим ряд примеров:
б) Примеры рекурсивного задания функций



Здесь нетрудно сообразить, что (n)=n.



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

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

n!  (2n)1/2*(nn)/(en)


Эта рекурсивная функция определяет числа Фибоначчи: 1 1 2 3 5 8 13, которые достаточно часто возникают при анализе различных задач, в том числе и при анализе алгоритмов. Отметим, что асимптотически (n) [1,618n] [9].



Для получения функции в явном виде рассмотрим ее последовательные значения: (0)=1, (1)=2, (2)=4, (3)=8, что позволяет предположить, что (n)=2n, точноедоказательство выполняется по индукции.



Мы имеем дело с примером того, что одна и та же функция может иметь различные рекурсивные определения – (n)=2n, как и в примере 4, что проверяется элементарной подстановкой.



В этом случае мы можем получить решение в замкнутой форме, сопоставив значениям функции соответствующие степени двойки:

(2) = 2 = 21
(3) = 4 = 22
(4) = 8 = 23
(5) = 32 =25
(6) = 256 = 28

Обозначив через Fn – n -ое число Фибоначчи, имеем: (n)=2Fn.

2 РЕКУРСИВНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ

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

F(n);
If n=0 or n=1 (проверка возможности прямого вычисления)
Then F  1 Else
F n*F(n-1); (рекурсивный вызов функции)
Return (F);
End;

Анализ трудоемкости рекурсивных реализаций алгоритмов, очевидно, связан как с количеством операций, выполняемых при одном вызове функции, так и с количеством таких вызовов. Графическое представление порождаемой данным алгоритмом цепочки рекурсивных вызовов называется деревом рекурсивных вызовов. Более...
tracking img