关于递归和Lambda，用Fixed Point Combinator实现
为了简化起见，我们用一个最简单的递归例子来展开讨论。
计算 sum(1 to n)，f(n) (n > 0，不考虑负数)可以表达为：
f = 1 when n = 1, f = n + f(n - 1) when n > 1。
一上来，很多人肯定想到这么写：
Func<int, int> f = x => { if (x == 1) return 1; else return x + f(x - 1); };static Func<T, TReturn> FixedPointCombinator<T, TReturn>(Func<Func<T, TReturn>, Func<T, TReturn>> func){}static Func<T, TReturn> FixedPointCombinator<T, TReturn>(Func<Func<T, TReturn>, Func<T, TReturn>> func){ return x => func(FixedPointCombinator(func))(x);}static void Main(string[] args){ var func = FixedPointCombinator<int, int>(f => x => { if (x == 1) return 1; else return x + f(x - 1); }); Console.WriteLine(func(100)); }using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{ class Program { static Func<T, TReturn> FixedPointCombinator<T, TReturn>(Func<Func<T, TReturn>, Func<T, TReturn>> func) { return x => func(FixedPointCombinator(func))(x); } static void Main(string[] args) { var func = FixedPointCombinator<int, int>(f => x => { if (x == 1) return 1; else return x + f(x - 1); }); Console.WriteLine(func(100)); } }}
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{ class Program { static void Main(string[] args) { var func = null;//先声明为null就可以嵌套，编译通过了 func = f => x => (x == 1)?1:x + func(x - 1); }; Console.WriteLine(func(100)); } }}
[解决办法]
擦。多了
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication1{ class Program { static void Main(string[] args) { var func = null;//先声明为null就可以嵌套，编译通过了 func = x => (x == 1)?1:x + func(x - 1); }; Console.WriteLine(func(100)); } }}
[解决办法]
func = x => (x == 1) ? 1 : x + func(x - 1);
er...
没编译器。再修改一次。
[解决办法]
//以前看到的using System;using System.Collections.Generic;public class Test{delegate T SelfApplicable<T>(SelfApplicable<T> self);private static void Main(){ SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>> Y = y => f => x => f(y(y)(f))(x); Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> Fix = Y(Y); Func<Func<int, int>, Func<int, int>> F = fac => x => x == 0 ? 1 : x * fac(x - 1); Func<int, int> factorial = Fix(F); System.Console.WriteLine(factorial(4).ToString());}}
[解决办法]
引用您的原话：
但是大多数人，比如我，数学很菜。所以我想试着帮助老赵来解释下。
为什么是这样的逻辑呢？数学越不好=》越应该去解释这种问题？呵呵，可能是我文科不好，没能理解您深层次上的逻辑=》数学越不好=》越应该去解释技术问题，但是就我个人看来感觉罗嗦上有点别扭！但是也许这么说也是没错的！
不好意思，如果是我指正错误，就当我没说！
[解决办法]
static void Main(string[] args) { //这里要注意！！ //必须要先赋值后才可以进行递归定义。否则会编译出错 Func<int, int> fac = null; fac = (x => x == 0 ? 1 : x * fac(x - 1)); for (int i = 0; i < 10; i++) { Console.WriteLine("{0} : {1}", i, fac(i)); } }
[解决办法]
既然这样你不如去学F#，F#解决这类问题更优雅...前两年研究了几天，后来没心思看了...
[解决办法]
这是产生式编程得一个非常特别得例子，特别之处在于，他是最普通，最本质得，所以，是非常特别得函数，
而元编程含义大于产生式编程，产生式编程是人类，元编程是人类社会！！！！！！！！！！！！
[解决办法]
同意Func<int, int> f = null;f = x => x == 1 ? 1 : x + f(x - 1);
[解决办法]
所有得递归问题都可以转换成递推得推论是，任何一个功能，能被动态产生得递推实现，而这个动态产生式可以是一个字符串，而字符串，有可以被任意替换，这就是说任何一个功能可以被动态得替换成另一个功能！！！！！！！！！！！！！！！！！！！！！！！！！
[解决办法]
http://hi.baidu.com/feixue/blog/item/e809baa1bd3c549c47106429.html
在参考了本贴及其它资料后的总结：
本文主要总结了一些资料中对Y组合子的推导,最后参考其中一份C#代码,并给出了C++0x中的实现.
个人认为,直真正实现Y组合子的是文中出现的第一份C#代码,其它的实现借助了对函数递归的支持.
1.直接递归不行,因为在定义中出现了自己;
2.通过参数的形式把递归的部分传进去(记为F);
3.假设目标为f,于是F(f) = f,问题转换为求F的不动点;
4.知道高阶Fix满足性质:Fix(F) = F(Fix(F)),现在目标是找到这样的Fix;
5.两个推导思路
5.1
构造一个式子,使之满足F(f) = f;
如果具有A(b) = F(b(b))的形式的函数则w(A) = F(w(A));
如果构造一个函数以F为参数，返回w(A)则就是Y组合子;
得到Y = g => (b=>g(b(b))) (b=>g(b(b))).
5.2
构造一个组合子Y,接受一个参数y表示本身,还有一个参数f表示一个高阶函数,使得能
返回f的不动点;
于是Y有形式Y = y => f => ???;
根据定义???部分就是:y(y)(f);
但是现在的结果平凡的,只是没有意义地展开,注意到不动点性质,于是???可以是
f(y(y)(f));
但是上面得到的结果在惰性计算的情况下才可行,于是要构造一个传值的:
Y = y => f => x => f(y(y)(f))(x);
于是最后Y(Y)为所求.
6.根据5.2在C#中的实现.
首先Y的类型的参数类型和Y一样于是:
delegate T SelfApplicable<T>(SelfApplicable<T> self)
这样就构造了一个委托,其参数类型是自身,返回类型待定.
注意到5.2中的结果:
f => x => f(y(y)(f))(x);是返回的表达式,这个表达式的类型是
Func<int, int>
f的类型可以2推导出来.
fac => x => x == 0 ? 1 : x * fac(x - 1);
可以看到参数类型是fac : Func<int, int>
返回类型是: Func<int, int>
于是最后的T : Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>
得到如下C#代码:
using System;using System.Collections.Generic;public class Test{delegate T SelfApplicable<T>(SelfApplicable<T> self);private static void Main(){ SelfApplicable<Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>>> Y = y => f => x => f(y(y)(f))(x); Func<Func<Func<int, int>, Func<int, int>>, Func<int, int>> Fix = Y(Y); Func<Func<int, int>, Func<int, int>> F = fac => x => x == 0 ? 1 : x * fac(x - 1); Func<int, int> factorial = Fix(F); System.Console.WriteLine(factorial(4).ToString());}}
[解决办法]
装配脑袋有些纠结于vb.net，所以对以前版本的vb.net对lamda只支持单行而不支持c#那种多行（例如
Func<int, int> f = x =>{ var result = 0;begin: result += x; if (x == 1) return result; else { x--; goto begin; }};
[解决办法]
Func<int, int> f = x => { if (x == 1) return 1; else return x + f(x - 1); };
[解决办法]
既然只是编译器造成的问题（而不是运行时的问题），这就非常好解决，而不必使用很复杂的理论（我相信所有人都喜欢简单的方法办大事，而不喜欢复杂的方法办小事）。在一个需要lamda表达式得地方，如果你觉得不好写，那么就另外写一个实名的函数，然后在这个需要lamda表达式的地方调用它（或者表达式其中一部分调用它）这就行了。除非我们遇到了不允许编写自定义函数的开发平台，才需要去研究更复杂的理论。
[解决办法]
//c++中，虽然在定义语句中并没有完全定义，但是在里面这个标识符已经可以用了//以前论坛中有人提到过的一个问题就是int x = x;何解function<int (int)> fac = [&](int x)->int{return x == 0 ? 1 : x * fac(x-1);};