Рекурсивные алгоритмы и их функции реферат

Обновлено: 02.07.2024

Прикрепленные файлы: 1 файл

Рекурсивные алгориты.doc

Дерево

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

Связь с левым потомком

Связь с правым потомком

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

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

TYPE Вершина = POINTER TO Элемент ;

PROCEDURE Смеш_Обход (K : Вершина);

Смеш_Обход (K^.LLink); (* Обход левого поддерева *)

WriteCard (K^.Info); (* Обработка корня *)

Смеш_Обход (K^.RLink); (* Обход правого поддерева *)

В традиционном программировании рекурсия часто рассматривается как некоторый заменитель итерации. Причем в качестве примеров рассматривается вычисление рекуррентных последовательностей, которые могут быть легко сформированы и обычными итераторами (циклами WHILE, REPEAT и т.п.). Природа рекурсии значительно глубже, чем механизм итерации, поэтому ее использование практически не имеет альтернатив в виде итераторов только тогда, когда решение задач проводится на рекурсивных структурах. Попробуйте написать процедуру Смеш-Обход без использования рекурсии, только на основе циклов и, если Вам это удастся, сравните ее с приведенным выше вариантом рекурсивной процедуры по наглядности, лаконичности, выразительности.

Преимущества и недостатки рекурсивного алгоритма

Современные информационные технологии содержат достаточно средств, чтобы сделать теоретически эффективные рекурсивные алгоритмы, также эффективными и широко используемыми на практике.

Преимущества рекурсии заключается в следующих аспектах:

Недостатки рекурсии заключаются в следующем:

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

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

Примеры решения задач с помощью рекурсии

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

Решение: На площадке (назовем ее А) находится пирамида, составленная из дисков уменьшающегося от основания к вершине размера.

Эту пирамиду в том же виде требуется переместить на площадку В. При выполнении этой работы необходимо соблюдать следующие ограничения:

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

Нетрудно решить эту задачу для двух дисков. Обозначая перемещения диска, например, с площадки А на В так: А→В. Напишем алгоритм для этого случая: А→С; А→В; С→В. Всего 3 хода.

Для трех дисков алгоритм длиннее: А→В; А→С; В→С; А→В; С→А; С→В; А→В. В этом случае уже требуется 7 ходов.

Подсчитать количество ходов (N) для k дисков можно по следующей рекуррентной формуле: N(k)=2xN(k-1)+1.

Например, N(10)=1023, N(20)=104857. А вот сколько перемещений нужно сделать ханойским монахам: N(64)=18446744073709551615.

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

Алгоритм решения задачи будет следующим:

1)Если N=0, то ничего не делать.

2)Если N>0, то переместить (N-1) диск на С через В;

● Переместить диск с А на В (А→В);

● Переместить (N-1) диск с С на В через А.

При выполнении пункта 2 последовательно будем иметь три состояния.

Описание алгоритма имеет явно рекурсивный характер.

А теперь построим программу на Паскале. В ней имеется рекурсивная процедура Hanoy, выполнение которой заканчивается только при N=0. При обращении к процедуре используются фактические имена площадок, заданные их номерами: 1, 2, 3. Поэтому на выходе цепочка перемещений будет описываться в таком виде: 1→2; 1→3; 2→3 и т.д.

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

Рубрика	Программирование, компьютеры и кибернетика
Вид	реферат
Язык	русский
Дата добавления	12.07.2010
Размер файла	62,6 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

Реферат на тему:

СОДЕРЖАНИЕ

1 Рекурсивные функции

2 Рекурсивная реализация алгоритмов

3 Анализ трудоемкости механизма вызова процедуры

4 Анализ трудоемкости алгоритма вычисления факториала

5 Логарифмические тождества

6 Методы решения рекурсивных соотношений

7 Рекурсивные алгоритмы

8 Основная теорема о рекуррентных соотношениях

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

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

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

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

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

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

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

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

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

n! (2 n) 1/2 *(n n )/(e n )

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

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

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

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

(2) = 2 = 2 1

(3) = 4 = 2 2

(4) = 8 = 2 3

(5) = 32 = 2 5

(6) = 256 = 2 8

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

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

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

Рассмотрим пример рекурсивной функции, вычисляющий факториал:

F(n);

If n=0 or n=1 (проверка возможности прямого вычисления)

Then F 1 Else

F n*F(n-1); (рекурсивный вызов функции)

Return (F);

End;

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

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

Рассмотрим пример для функции вычисления факториала (рис 1):

Рисунок 1 - Дерево рекурсии при вычислении факториала - F(5)

Дерево рекурсивных вызовов может иметь и более сложную структуру, если на каждом вызове порождается несколько обращений - фрагмент дерева рекурсий для чисел Фибоначчи представлен на рис 2:

Рисунок 2 - Фрагмент дерева рекурсии при вычислении чисел Фибоначчи - F(5)

3 АНАЛИЗ ТРУДОЕМКОСТИ МЕХАНИЗМА ВЫЗОВА ПРОЦЕДУРЫ

Механизм вызова функции или процедуры в языке высокого уровня существенно зависит от архитектуры компьютера и операционной системы. В рамках IBM PC совместимых компьютеров этот механизм реализован через программный стек. Как передаваемые в процедуру или функцию фактические параметры, так и возвращаемые из них значения помещаются в программный стек специальными командами процессора. Дополнительно сохраняются значения необходимых регистров и адрес возврата в вызывающую процедуру. Схематично этот механизм иллюстрирован на рис 3.

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

Рисунок 3 - Механизм вызова процедуры с использованием программного стека

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

m - количество передаваемых фактических параметров,

k - количество возвращаемых процедурой значений,

r - количество сохраняемых в стеке регистров, имеем:

f_вызова = m+k+r+1+m+k+r+1 = 2*(m+k+r+1) элементарных операций на один вызов и возврат.

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

4 АНАЛИЗ ТРУДОЕМКОСТИ АЛГОРИТМА ВЫЧИСЛЕНИЯ ФАКТОРИАЛА

Для рассмотренного выше рекурсивного алгоритма вычисления факториала количество вершин рекурсивного дерева равно, очевидно, n, при этом передается и возвращается по одному значению (m=1, k=1), в предположении о сохранении четырех регистров - r=4, а на последнем рекурсивном вызове значение функции вычисляется непосредственно - в итоге:

f_A(n)=n*2*(1+1+4+1)+(n-1)*(1+3)+1*2=18*n - 2

Отметим, что n - параметр алгоритма, а не количество слов на входе.

5 ЛОГАРИФМИЧЕСКИЕ ТОЖДЕСТВА

При анализе рекурсивных алгоритмов достаточно часто используются логарифмические тождества, далее предполагается, что, a > 0, b > 0, c > 0, основание логарифма не равно единице:

b logba = a;

e lnx = x;

log_b a c = c * log_b a;

log_b a = 1/log_a b

log_b a = log_c a / log_c b в записи (ln(x)) основание логарифма не существенно, если он больше единицы, т.к. константа скрывается обозначением .

a log b c =c log b a

Можно показать, что для любого > 0 ln(n )= о(n ), при n

6 МЕТОДЫ РЕШЕНИЯ РЕКУРСИВНЫХ СООТНОШЕНИЙ

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

а) Метод индукции. Метод состоит в том, что бы сначала угадать решение, а затем доказать его правильность по индукции. Пример:

(n+1)=2*f(n)

Предположение: (n)=2 n

Базис: если (n)=2 n , то (0)=1, что выполнено по определению.

Индукция: Пусть (n)=2 n , тогда для n+1 (n+1)= 2 * 2 n =2 n +1

Заметим, что базис существенно влияет на решение, так, например. Если (0)=0, то (n)=0;если (0)=1/7, то (n)=(1/7)*2 n ; если (0)=1/64, то (n)=(2) n-6

б) Метод итерации (подстановки). Суть метода состоит в последовательной подстановке - итерации рекурсивного определения, с последующим выявлением общих закономерностей. Пусть (n)=3*(n/4)+n, тогда:

(n)=n+3*(n/4)=n+3*[n/4+3*(n/16)]=n+3* [n/4+3 n/16+3*(n/64) >],

и раскрывая скобки, получаем:

(n)=n+3*n/4+9*n/16+27*n/64+…+3 i *n/4 i

Остановка рекурсии произойдет при (n / 4 i ) 1 i log₄ n, в этом случае последнее слагаемое не больше, чем 3 log 4 n * (1) = n log 4 3 * (1).

(n) = n* (3/4) k + n log 4 3 * (1), т.к. (3/4) k = 4*n, то окончательно:

(n) = 4 * n + n log4 3 * (1) = (n)

7 РЕКУРСИВНЫЕ АЛГОРИТМЫ

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

В общем виде, если происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b, то общий вид функции трудоемкости имеет вид:

f_A(n )= a * f_A( n/b )+d(n)+U(n) (9.1),

где d(n) - трудоемкость алгоритма деления задачи на подзадачи,

U(n) - трудоемкость алгоритма объединения полученных решений.

Рассмотрим, например, известный алгоритм сортировки слиянием, принадлежащий Дж. Фон Нейману [6]:

На каждом рекурсивном вызове переданный массив делится пополам, что дает оценку для d(n) = (1), далее рекурсивно вызываем сортировку полученных массивов половинной длины (до тех пор, пока длина массива не станет равной единице), и сливаем возвращенные отсортированные массивы за (n).

Тогда ожидаемая трудоемкость на сортировку составит:

f_A(n )= 2 * f_A( n/2 )+ (1)+ (n)

Тем самым возникает задача о получении оценки сложности функции трудоемкости, для произвольных значений a и b.

8 ОСНОВНАЯ ТЕОРЕМА О РЕКУРРЕНТНЫХ СООТНОШЕНИЯХ

Следующая теорема принадлежит Дж. Бентли, Д. Хакен и Дж. Саксу (1980 г.). Теорема. Пусть a 1, b > 1 - константы, g(n) - функция, пусть далее:

(n)=a*(n/b)+g(n), где n/b = (n/b) или (n/b)

1) Если g(n) = O(n logba- ), >0, то (n)= (n logba )

Пример:(n) = 8(n/2)+n 2 , тогда (n) = (n 3 )

2) Если g(n)= (n log6a ), то (n)= (n logba *log n)

Пример: f_A(n)= 2 * f_A( n/2 )+ (n), тогда (n) = (n*log n)

3) Если g(n) = (n logba+e ), e > 0, то (n) = (g(n))

Пример: (n)=2*(n/2)+n 2 , имеем:

n logba = n 1 , и следовательно: (n) = (n 2 )

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

Подобные документы

История развития средств вычислительной техники. Машина Тьюринга: понятие и свойства. Теория переменных и типов данных в ANSI C. Обменные сортировки, их виды. Исходный, объектный и машинный код. Функции компилятора и линковщика. Рекурсивные алгоритмы.

шпаргалка [432,5 K], добавлен 04.05.2015

Определение понятия графа как набора вершин и связей между ними. Способы решения задач по программированию согласно теории графов на примерах заданий "Дороги", "Перекрестки", "Скрудж Мак-Дак", используя рекурсивные функции и рекуррентные соотношения.

курсовая работа [36,2 K], добавлен 10.03.2010

Использование рекурсии в предметных областях. Рекурсивные процедуры и функции в программировании. Создание алгоритмов для рисования графических изображений с использованием рекурсии в среде программирования Pascal ABC. Примеры рекурсии в графике.

творческая работа [6,7 M], добавлен 01.02.2014

Классификация и стек рекурсивных функций. Методика распознавания формулы, записанной в строке. Реализация салфетки Серпинского и задачи о Ханойских башнях. Алгоритм быстрой сортировки. Создание функции, сортирующей массив с использованием рекурсии.

лабораторная работа [160,8 K], добавлен 06.07.2009

Методы и алгоритмы вычисления определенных интегралов: метод трапеций и метод Симпсона (метод парабол). Оформление функции вычисления заданного определённого интеграла на Visual Basic 6.0. Программный код функции. Создание приложения для вычисления.

курсовая работа [483,6 K], добавлен 25.06.2014

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

курсовая работа [228,7 K], добавлен 14.10.2017

Структура языка Паскаль, встроенные процедуры и функции. Составление алгоритма решения уравнения, описывающего работу кривошипно-шатунного механизма, с помошью метода итерации, метода Гаусса и метода Зейделя. Блок-схемы алгоритмов и текст программы.

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

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

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

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

Под индукцией понимается метод доказательства утверждений сформулировкой зависящей от натурального переменного или и проводитсядоказательство для

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

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

Последние двадцать лет получили бурное развитие созданная иглубоко развитая Бенуа Мандельбротом фрактальная геометрия, теориямультифракталов и их приложения. Нужно заметить, что в теориях понятие рекурсииодно из основных. Так, например, многие фрактальные геометрические фигуры,такие как совершенное канторово множество или салфетка Серпинского,определяются рекурсивно [1]

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

Теория рекурсивных алгоритмов.

Задача точного определения понятия алгоритма былаполностью решена в 30-х годах XXвека в двух формах: на основе описания алгоритмическогопроцесса и на основе понятия рекурсивной функции.

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

Развитие теории конечных автоматов позволилострого доказать алгоритмическую неразрешимость ряда важных математическихпроблем (10-й проблемы Гильберта [3]

, проблемы представимости матриц [4] и др.). Однако еёсущественным недостатком является невозможность реализации такой полезнойконструкции как рекурсия.

Этого недостатка лишён другой подход кформализации понятия алгоритма, развитый Гёделем и Чёрчем. Здесь теорияпостроена на основе широкого класса так называемых частично рекурсивных функций [5]

Замечателен тот факт, что оба данных подхода, атакже другие подходы (Марков, Пост) приводят к одному и тому же классу алгоритмическивычислимых функций [6]

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

Сначала определим иисследуем сам класс частично рекурсивных функций [7].Данный класс определяется путем указания конкретных исходных функций ификсированного множества операций получения новых функций из заданных.

В качестве базисныхфункций обычно берутся следующие:

2. Функция следования:

3. Функция выборааргументов:

Допустимыми операцияминад функциями являются операции суперпозиции (подстановки), рекурсии и минимизации.

Операция суперпозиции. Пусть даны и функций зависят от одних и техже переменных .Это можносделать путем введения фиктивных переменных. Суперпозицией (подстановкой)функций и называется функция

Функция на наборе переменных определена тогда и толькотогда, когда определены все функции и функция определена на наборе Операциюсуперпозиции обозначают:

Операция рекурсии(точнее: примитивнойрекурсии). Пусть заданы и индуктивным образом спомощью соотношений:

Ясно, что данные соотношенияоднозначно определяют функцию считается определённой в том и тольков том случае, когда определены и при неопределено, то и неопределено при Про функцию говорят, чтоона получена рекурсией из функций и

Операция минимизации. Пусть задана и рассмотрим уравнениеотносительно

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

Функция называется частично-рекурсивной,если она может быть получена из базисных функций ,, применением конечногочисла раз операций суперпозиции, рекурсии и минимизации.

Определение [9].Функция называется алгоритмически вычислимой, если существует алгоритмнахождения значения функции при любом допустимом значении аргумента.

Очевидно, что функции, и алгоритмически вычислимы.Можно доказать, что операции суперпозиции, рекурсии и минимизации сохраняют свойствовычислимости [10].Значит, все частично рекурсивные функции вычислимы. Тезис Чёрча утверждает, чтокласс алгоритмически вычислимых функций совпадает с классом всех частичнорекурсивных функций. То есть выполняется и обратное включение: все вычислимые функциичастично рекурсивны. Принятие данного тезиса позволяет истолковыватьдоказательство, что некоторая функция не является частично рекурсивной, какдоказательство отсутствия алгоритма вычисления ее значений.

Аппарат частичнорекурсивных функций позволяет исследовать общие алгоритмические проблемы. Дляэтого используется метод характеристик. Он заключается в следующем. Поконкретной задаче строится соответствующая характеристическая функция, которая затемизучается на вычислимость. Вычислимость её позволяет утверждать разрешимостьисходной проблемы. Пусть, например, стоит проблема разрешения предиката [11].То есть если задан

или доказать, что такого алгоритма нет. Составляем характеристическую функцию:

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

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

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

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

1.Умножение битовых операций.Предложим рекурсивный алгоритм для данной задачи. Пусть и — два и на две равные части ввиде и будем рассматриватькаждую часть как можно представить ввиде

Равенство дает способ вычисления произведения с помощью четырех умножении

где Ясно, что операции сложения исдвига имеют сложность .

Заметим, что и имеют, вообще говоря, разрядов. Тогда

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

Таким образом, числоиспользуемых операций ограничено сверху

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

2.Умножение матриц. Даны две квадратные матрицы порядка с элементами из некоторогокольца и требуетсянайти их произведение. Стандартный алгоритмтребует умножений и К. На первый взгляд, кажется, чтоневозможно сколько-нибудь существенно уменьшить данное число операций, Однако, В.Штрассеном [13] былпредложен следующий алгоритм.

Пусть и даны матрицы может быть вычисленатак. Пусть , .

Заметим, в данномалгоритме использовано 7 умножений и 18 сложений и не использованакоммутативность умножения.

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

Пусть — число арифметическихопераций, используемых в алгоритме на матрицах размера и и формула справедлива.Пусть для формула действительноследует из соотношений. Имеем при т.е. наша формула справедливаи для

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

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

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

где — фиксированные целыечисла.

Теперь можно доказать,что справедливо следующее утверждение [15].Пусть дано рекуррентное соотношение

где — фиксированныеконстанты. Тогда при

Далее вытекаетследствие [16],что в предположениях предыдущего утверждения справедливы соотношения

В некоторых случаяхрекурсию для задачи размера удаётся организоватьтолько путем аддитивного уменьшения исходного размера задачи на некоторую константу такого типарекурсивных алгоритмов определяется рекуррентным соотношением вида

где — фиксированныеконстанты. Например, такая ситуация возникает при решении графических задач.Для такого соотношения при [17]

где — фиксированныеконстанты. Оно определяет однозначно функцию при таким выражением [18]

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

Для задачи умноженияматриц использование базового алгоритма умножения умножениями дляпостроения рекурсивного алгоритма, сводящего умножение

(в алгоритме Штрассена и и получил еще не решена [19].

Рассмотрим еще один примерприменения полученных результатов. Вернемся к задаче умножения чисел в двоичнойзаписи. Зафиксируем натуральное число и рассмотрим два и

ГОСТ

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

Рекурсивные алгоритмы

Под рекурсией понимается способ представления типа объектов или методов путём предварительного задания одного или больше (как правило упрощённых) его основных случаев или методик, а далее представлением на их базе правил формирования рассматриваемого типа, которые непосредственно или опосредовано ссылаются на эти основные случаи.

По-иному, рекурсия — это метод обобщённого представления объекта или воздействия через самого себя, с применением задаваемых раньше конкретных определений.

Готовые работы на аналогичную тему

Если число колец больше:

Используя рекурсию переместите все кольца, за исключением одного, из источника в запас, применяя приёмник в качестве запаса.
Переместите последнее кольцо из источника в приёмник.
Переместите все кольца из запаса в приёмник, применяя источник в качестве запаса.

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

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

К примеру программная функция А обращается к функции В, а функция В обращается к функции А. Число вложенных обращений к функциям или процедурам следует называть глубиной рекурсии.

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

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

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

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

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

Читайте также: