Анонимная рекурсия на C# и лямбды

Лямбды есть анонимные функции, а рекурсия требует определения имен.
Определение функции, которая вычисляет число Фибоначчи:

Func fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;

Но работать это не будет, т.к. компилятор выдаст ошибку:

Use of unassigned local variable 'fib'

Проблема в том, что правая сторона выражения оценивается до того, как fib будет определена.

Быстрый обход этой проблемы - присвоить fib null, то есть явно определить fib перед тем, как она будет использована.

Func fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Console.WriteLine(fib(6));                        // displays 8

Но это решение не является настоящей рекурсией. Рекурсия требует, чтобы функция вызывала саму себя. В данном случае функция fib просто вызывает делегат, на который ссылается локальная переменная fib. На первый вгзгляд, это игра слов, но рассмотрим следующий пример:

Func fib = null;
fib = n => n > 1 ? fib(n - 1) + fib(n - 2) : n;
Func fibCopy = fib;
Console.WriteLine(fib(6));                        // displays 8
Console.WriteLine(fibCopy(6));                    // displays 8
fib = n => n * 2;
Console.WriteLine(fib(6));                        // displays 12
Console.WriteLine(fibCopy(6));                    // displays 18

Можно заметить, как меняется результат вызова fib и даже вызов fibCopy отличается от вызова fib. Этот беспредел можно остановить, передавая функцию, которая будет использоваться для рекурсивного вызова:

(f, n) => n > 1 ? f(f,n - 1) + f(f,n - 2) : n

Таким образом, лямбда выглядит почти так же за тем исключением, что она первым параметром принимает функцию f. Когда вызывается фунцкия f, нужно передать ее в себя первым аргументом.

Чтобы это реализовать и преобразовать лямбду к делегату, необходимо определить тип делегата. Начнем с типа fib, Func. Возвращаемый тип - int, принимаемым вторым аргументов типом также должен быть int. Что касается первого аргумента, им должен быть делегат, который должен вызываться с теми же аргументами, которые мы определяем в данном случае, что и есть рекурсия:

delegate int Recursive(Recursive r, int n);

Этот делегат можно обобщить через параметризацию аргумента и возвращаемого типа:

delegate R Recursive(Recursive r, A a);

Теперь можно использовать лямбду, определенную выше:

Recursive fib = (f, n) => n > 1 ? f(f,n - 1) + f(f,n - 2) : n;
Console.WriteLine(fib(fib,6));                      // displays 8

Хотя это является решением, выглядит оно не так красиво, как первоначальный код...

(продолжение следует)