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


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

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

Классы CTS
Извлечение данных XML из баз данных SQL Server 2000
Применение событий формы
Циклические ссылки
Обработка ошибок при обновлении базы данных
Пространства имен System.Drawing
Проверка на уровне формы
Промежуточный язык
Работа в редакторе кода
Принципы дизайна интерфейса
Проверка на уровне поля
Отладка элементов управления
Parsing Expression Grammar Support for C# 3.0 Part 1 – PEG Lib and Parser Generator
Установка сборок в GAC
Использование отладочных инструментов
| .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 | Рекурсия. Регион сайта: Москва и Санкт-Петербург