Основы программирования на C#


Рекурсия - часть 2


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

public void TestTailRec() { Hanoi han = new Hanoi(5); long time1, time2; long f=0; time1 = getTimeInMilliseconds(); for(int i = 1; i <1000000; i++)f =han.fact(15); time2 =getTimeInMilliseconds(); Console.WriteLine(" f= {0}, " + "Время работы циклической процедуры: {1}",f,time2 -time1); time1 = getTimeInMilliseconds(); for(int i = 1; i <1000000; i++)f =han.factorial(15); time2 =getTimeInMilliseconds(); Console.WriteLine(" f= {0}, " + "Время работы рекурсивной процедуры: {1}",f,time2 -time1); }

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

Проводить сравнение эффективности работы различных вариантов - это частый прием, используемый при разработке программ. И я им буду пользоваться неоднократно. Встроенный тип DateTime обеспечивает необходимую поддержку для получения текущего времени. Он совершенно необходим, когда приходится работать с датами. Я не буду подробно описывать его многочисленные статические и динамические методы и свойства. Ограничусь лишь приведением функции, которую я написал для получения текущего времени, измеряемого в миллисекундах. Статический метод Now класса DateTime возвращает объект этого класса, соответствующий дате и времени в момент создания объекта. Многочисленные свойства этого объекта позволяют извлечь требуемые характеристики. Приведу текст функции getTimeInMilliseconds:

long getTimeInMilliseconds() { DateTime time = DateTime.Now; return(((time.Hour*60 + time.Minute)*60 + time.Second)*1000 + time.Millisecond); }

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

Сравнение времени работы циклической и рекурсивной функций

Рис. 10.1.  Сравнение времени работы циклической и рекурсивной функций

Вовсе не обязательно, что рекурсивные методы будут работать медленнее нерекурсивных. Классическим примером являются методы сортировки. Известно, что время работы нерекурсивной пузырьковой сортировки имеет порядок c*n2, где c - некоторая константа. Для рекурсивной процедуры сортировки слиянием время работы - q*n*log(n), где q - константа. Понятно, что для больших n сортировка слиянием работает быстрее, независимо от соотношения значений констант. Сортировка слиянием - хороший пример применения рекурсивных методов. Она демонстрирует известный прием, называемый "разделяй и властвуй". Его суть в том, что исходная задача разбивается на подзадачи меньшей размерности, допускающие решение тем же алгоритмом. Решения отдельных подзадач затем объединяются, давая решение исходной задачи. В задаче сортировки исходный массив размерности n можно разбить на два массива размерности n/2, для каждого из которых рекурсивно вызывается метод сортировки слиянием. Полученные отсортированные массивы сливаются в единый массив с сохранением упорядоченности.

На примере сортировки слиянием покажем, как можно оценить время работы рекурсивной процедуры. Обозначим через T(n) время работы процедуры на массиве размерности n. Учитывая, что слияние можно выполнить за линейное время, справедливо следующее соотношение:

T(n) = 2T(n/2) + cn

Предположим для простоты, что n задается степенью числа 2, то есть n = 2k. Тогда наше соотношение имеет вид:

T(2k) = 2T(2k-1) + c2k

Полагая, что T(1) =c, путем несложных преобразований, используя индукцию, можно получить окончательный результат:

T(2k) = c*k*2k = c*n*log(n)

Известно, что это - лучшее по порядку время решения задачи сортировки. Когда исходную задачу удается разделить на подзадачи одинаковой размерности, то, при условии существования линейного алгоритма слияния, рекурсивный алгоритм имеет аналогичный порядок сложности. К сожалению, не всегда удается исходную задачу разбить на k подзадач одинаковой размерности n/k. Часто такое разбиение не представляется возможным.




Начало  Назад  Вперед



Книжный магазин