* При перепечатке материалов ссылка на www.SeoLiga.ru обязательна!
Рекурсия
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(); } Как ты заметил, здесь используется аккумулятор, т.е. переменная, в которой накапливается результат, это значительно экономит используемую память, т.к. память при этом расходуется только на хранение адресов возврата значения функции. Кроме того любой сносный компилятор пребразует эту рекурсию в обычный цикл. Ты спросишь, зачем тогда нужна рекурсия, если компилятор всё равно в лучшем случае преобразует её в цикл, но этот вопрос выходит за рамки данной статьи и как говорится, чтобы понять рекурсию, нужно сначала понять рекурсию. так что идём дальше...
