Имя Пароль
Зарегистрироваться


* При перепечатке материалов ссылка на www.SeoLiga.ru обязательна! RSS



Рекурсия
6 февраля 2009

Это вероятно самое раннее заимствование из ФП. В императивных языках для многократного выполнения некоторого кода используют циклы, ФП для этой цели использует рекурсию. Так вот, многие из вас видели классический пример рекурсии - вычисление факториала, но я думаю немногие знают, что в нём содержится императивная ошибка, да он работает, однако писать нечто типа N*Factorial(N-1) это мягко говоря не разумно. Восстановим справедливость и напишем правильный вариант в функциональном стиле на C# с использованием хвостовой рекурсии:
static public long Factorial(int n, int acc)
{
if (n > 1) return Factorial(n - 1, n * acc);
else return acc;
}

static void Main(string[] args)
{
for (int i=0; i<10; i++)
Console.WriteLine("{0}! = {1}", i, Factorial(i, 1));
Console.ReadLine();
}
Как ты заметил, здесь используется аккумулятор, т.е. переменная, в которой накапливается результат, это значительно экономит используемую память, т.к. память при этом расходуется только на хранение адресов возврата значения функции. Кроме того любой сносный компилятор пребразует эту рекурсию в обычный цикл. Ты спросишь, зачем тогда нужна рекурсия, если компилятор всё равно в лучшем случае преобразует её в цикл, но этот вопрос выходит за рамки данной статьи и как говорится, чтобы понять рекурсию, нужно сначала понять рекурсию. так что идём дальше...


Теги: .NET

Статьи по теме:

Towards Cleaner Code, A C# Asynchronous Helper
Blend PDF with Silverlight
Модель защиты, основанная на ролях
События жизненного цикла формы
Обзор .NET Framework
Применение отладочных инструментов
Создание формируемых элементов управления
Вывод типов
Перегрузка членов
Создание проекта установочной программы
Создание элемента управления
Свойства-наборы
Делегаты
Вызов методов
Компонент PrintDocument
| .NET | Pavel |
 


Пн Вт Ср Чт Пт Сб Вс
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31


     



Rambler's Top100

Данный сайт или домен продается ICQ: 403-353-727

© 2009 Seoliga.ru | .NET | Рекурсия. Регион сайта: Москва и Санкт-Петербург