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


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

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

Окна Locals, Autos и Watch
Рисование простых фигур
Реализация обработчиков событий
Проект установочной программы
Редакторы свойств программы установки
Классы CTS
Объект Graphics
Типы значений и ссылочные типы
Компонент PrintDocument
Свойства BackColor, ForeColor и Text
Doxygen – версия 1.5.7
Мемоизация (memoization)
Ограничения Foreign Key
Применение объектов DataSet и обновление данных
Карринг (currying)
| .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


     



Rambler's Top100

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

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