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


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

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

Добавление формы к проекту
Получение и установка текущей культуры пользовательского интерфейса
CBitmapEx – C++-класс для работы с BMP
Наборы
Вложенные типы
Преобразование типов
Работа с несколькими результирующими наборами
Защита приложения
Модель защиты, основанная на ролях
Класс DataViewManager
Проверка на уровне формы
Редактор типов файлов
Абстрактные классы и члены
Применение методов формы
Распространение приложений через Интернет
| .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 | Рекурсия. Регион сайта: Москва и Санкт-Петербург