Автор работы: Пользователь скрыл имя, 13 Марта 2015 в 18:32, реферат
Рекурсивной называют функцию, которая прямо или косвенно сама вызывает себя.
Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна.
ТИТУЛЬНЫЙ ЛИСТ
Тема: Рекурсивные функции
Дисциплина: Основы теории алгоритмов
Рекурсивной называют функцию, которая прямо или косвенно сама вызывает себя.
Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащей прямой или косвенный вызов определяемой (первой) функции. В этом случае по тексту определения функции ее рекурсивность (косвенная) может быть не видна.
Если в теле функции явно используется вызов этой же функции, то имеет место прямая рекурсия.
Рекурсия называется однократной, если функция вызывает саму себя один раз. Если функция вызывает саму себя два раза, то рекурсия называется двукратной и т.д.
При каждом обращении к рекурсивной функции в стеке выделяется место для:
Схемой стека вызовов функций называется последовательность экземпляров функций, вызывающих друг друга.
Основное правило рекурсии: До рекурсивного вызова должна стоять проверка на возврат из рекурсии.
Большинство современных языков высокого уровня поддерживают механизм рекурсивного вызова, когда функция, как элемент структуры языка программирования, возвращающая вычисленное значение по своему имени, может вызывать сама себя с другим аргументом. Эта возможность позволяет напрямую реализовывать вычисление рекурсивно определенных функций. Отметим, что в силу тезиса Черча–Тьюринга аппарат рекурсивных функций Черча равномощен машине Тьюринга, и, следовательно, любой рекурсивный алгоритм может быть реализован итерационно.
Рассмотрим пример рекурсивной функции, вычисляющий факториал:
///
F(n);
If n=0 or n=1 (проверка возможности прямого вычисления)
Then F := 1 Else
F := n*F(n-1); (рекурсивный вызов функции)
Return (F);
End;
///
Анализ трудоемкости рекурсивных реализаций алгоритмов, очевидно, связан как с количеством операций, выполняемых при одном вызове функции, так и с количеством таких вызовов. Графическое представление порождаемой данным алгоритмом цепочки рекурсивных вызовов называется деревом рекурсивных вызовов. Более детальное рассмотрение приводит к необходимости учета затрат как на организацию вызова функции и передачи параметров, так и на возврат вычисленных значений и передачу управления в точку вызова.
Можно заметить, что некоторая ветвь дерева рекурсивных вызовов обрывается при достижении такого значения передаваемого параметра, при котором функция может быть вычислена непосредственно. Таким образом, рекурсия эквивалентна конструкции цикла, в котором каждый проход есть выполнение рекурсивной функции с заданным параметром.
Имеются три стержня с номерами 1, 2, 3. На стержень 1 надето n дисков различного диаметра так, что они образуют пирамиду. Написать программу для печати последовательности перемещений дисков со стержня на стержень, необходимых для переноса пирамиды со стержня 1 на стержень 3 при использовании стержня 2 в качестве вспомогательного. При этом за одно перемещение должен переноситься только один диск, и диск большего диаметра не должен помещаться на диск меньшего диаметра. Доказано, что для n дисков минимальное число необходимых перемещений равно 2n-1.
Для решения простейшего случая задачи, когда пирамида состоит только из одного диска, необходимо выполнить одно действие — перенести диск со стержня i на стержень j, что очевидно (этот перенос обозначается i -> j). Общий случай задачи изображен на рисунке, когда требуется перенести n дисков со стержня i на стержень j, считая стержень w вспомогательным. Сначала следует перенести n_1 диск со стержня i на стержень w при вспомогательном стержне j, затем перенести один диск со стержня i на стержень j и, наконец, перенести n_1 диск из w на стержень j, используя, вспомогательный стержень i. Итак, задача о переносе n дисков сводится к двум задачам о переносе n_1 диска и одной простейшей задаче. Схематически это можно записать так: T (n, i, j, w) = T (n_1, i, w, j), T (1, i, j, w), T (n_1, w, j, i).
Ниже приведена программа, которая вводит число n и печатает список перемещений, решающая задачу о Ханойских башнях при количестве дисков n. Используется внутренняя рекурсивная процедура tn (n, i, j, w), печатающая перемещения, необходимые для переноса n дисков со стержня i на стержень j с использованием вспомогательного стержня w при {i, j, w} = {1,3,2}.
///
#include <stdio.h>
void tn (int, int, int, int); /* функция */
main() /* вызывающая */
{
int n;
scanf (Вл%dВ»,&n);
tn (n, 1,2,3);
}
void tn (int n, int i, int j, int w) /* рекурсивная */
{
if (n>1) /* функция */
{
tn (n_1, i, w, j);
tn (1, i, j, w);
tn (n_1, w, j, i);
}
else
printf (В» \n % d ->%dВ», i, j);
return;
}
///
Каждый раз при вызове процедуры tn под параметры n, i, j, w выделяется память и запоминается место возврата. При возврате из процедуры tn память, выделенная под параметры n, i, j, w, освобождается и становится доступной память, выделенная под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.
Во многих случаях рекурсивные функции можно заменить на эквивалентные нерекурсивные функции или фрагменты, используя стеки для хранения точек вызова и вспомогательных переменных.
Механизм вызова функции или процедуры в языке высокого уровня существенно зависит от архитектуры компьютера и операционной системы. В рамках IBM PC совместимых компьютеров этот механизм реализован через программный стек. Как передаваемые в процедуру или функцию фактические параметры, так и возвращаемые из них значения помещаются в программный стек специальными командами процессора. Дополнительно сохраняются значения необходимых регистров и адрес возврата в вызывающую процедуру.
Для подсчета трудоемкости вызова будем считать операции помещения слова в стек и выталкивания из стека элементарными операциями в формальной системе. Тогда при вызове процедуры или функции в стек помещается адрес возврата, состояние необходимых регистров процессора, адреса возвращаемых значений и передаваемые параметры.
Анализ трудоемкости рекурсивных алгоритмов в части трудоемкости самого рекурсивного вызова можно выполнять разными способами в зависимости от того, как формируется итоговая сумма элементарных операций — рассмотрением в отдельности цепочки рекурсивных вызовов и возвратов, или совокупно по вершинам дерева рекурсивных вызовов.
Для рассмотренного выше рекурсивного алгоритма вычисления факториала количество вершин рекурсивного дерева равно, очевидно, n, при этом передается и возвращается по одному значению (m=1, k=1), в предположении о сохранении четырех регистров – r=4, а на последнем рекурсивном вызове значение функции вычисляется непосредственно – в итоге:
fA(n) = n*2*(1+1+4+1)+(n-1)*(1+3)+1*2=
Отметим, что n — параметр алгоритма, а не количество слов на входе.
Основной метод построения рекурсивных алгоритмов — это метод декомпозиции. Идея метода состоит в разделении задачи на части меньшей размерности, получение решение для полученных частей и объединение решений.
В общем виде, если происходит разделение задачи на b подзадач, которое приводит к необходимости решения a подзадач размерностью n/b, то общий вид функции трудоемкости имеет вид:
fA(n )= a * fA( n/b )+d(n)+U(n), где d(n) — трудоемкость алгоритма деления задачи на подзадачи, U(n) — трудоемкость алгоритма объединения полученных решений.
Следующая теорема принадлежит Дж. Бентли, Д. Хакен и Дж. Саксу (1980 г.).
Данная теорема является мощным средством анализа асимптотической сложности рекурсивных алгоритмов, к сожалению, она не дает возможности получить полный вид функции трудоемкости.