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


* При перепечатке материалов ссылка на 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

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

Automatically Starting your Application on Windows Mobile
Применение объектов DataSet и обновление данных
Создание экземпляров пользовательских типов
Создание DataAdapter с помощью окна Server Explorer
Реализация членов интерфейса на Visual C#
Члены типов CTS
Обработка и генерация исключений
Managed Control Panel Items
Модель защиты, основанная на ролях
Конфигурирование защиты по правам доступа к коду
Ресурсы и ресурсные сборки
Перечисления CTS
Отладка элементов управления
Стратегия оптимизации
Создание DataAdapter с помощью мастера Data Adapter Configuration Wizard
| .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 | Рекурсия. Регион сайта: Москва и Санкт-Петербург