Основы языка C# 2005. Евсеева О.Н - 94 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

98
Приведем вначале простейший пример рекурсивного определения
функции, вычисляющей факториал целого числа:
public long factorial(int n)
{
if (n <= 1)
return 1;
else
return n * factorial(n - 1);
} //factorial
Функция factorial является примером прямого рекурсивного определения
– в ее теле она сама себя вызывает. Здесь, как и положено, есть нерекурсивная
ветвь, завершающая вычисления, когда n становится равным единице. Это
пример так называемой «хвостовой» рекурсии, когда в теле встречается ровно
один рекурсивный вызов, стоящий в конце соответствующего выражения.
Хвостовую рекурсию намного проще записать в виде обычного цикла. Вот
циклическое определение той же функции:
public long fact(int n)
{
long res = 1;
for (int i = 2; i <= n; i++) res *= i;
return (res);
} //fact
Конечно, циклическое определение проще, понятнее и эффективнее, и
применять рекурсию в подобных ситуациях не следует. Интересно сравнить
время вычислений, дающее некоторое представление о том, насколько
эффективно реализуется рекурсия. Вот соответствующий тест, решающий эту
задачу:
public void TestTailRec() {
long time1, time2;
long f = 0;
time1 = getTimeInMilliseconds();
for (int i = 1; i < 1000000; i++) f = fact(15);
time2 = getTimeInMilliseconds();
Console.WriteLine(" f= {0}, " + "Время работы циклической процедуры:{1}",
f,time2 -time1);
time1 = getTimeInMilliseconds();
for (int i = 1; i < 1000000; i++) f = factorial(15);
time2 = getTimeInMilliseconds();
Console.WriteLine(" f= {0}, " + "Время работы рекурсивной процедуры:{1}",
f,time2 -time1);
}
Каждая из функций вызывается в цикле, работающем 1000000 раз. До
начала цикла и после его окончания вычисляется текущее время. Разность этих

Страницы