关于递归和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。

一上来，很多人肯定想到这么写：

C# code

Func<int, int> f = x => { if (x == 1) return 1; else return x + f(x - 1); };

结果编译器报错，使用f前没有初始化。

cnblog的装配脑袋给出了最佳实践，Fixed Point Combinator，不动点组合子。老赵也引用了这一做法，但是没有给出解释。当然，数学好的朋友理解起来不难，但是大多数人，比如我，数学很菜。所以我想试着帮助老赵来解释下。

这一做法的本质是，将递归展开变成递推函数，然后计算。
假设 x = 1，那么 f(x) 被调用 1 次。我的表述可能不正规，姑且记作 f1(1) = f(1) = 1
假设 x = 2，那么 f(x) 被调用 2 次，求 f(2) 的函数也可以表述成 f2(2) = 2 + f1(1) = 2 + 1
假设 x = 3，那么 f(x) 被调用 3 次，求 f(3) 的函数也可以表述成 f3(3) = 3 + f2(2) = 3 + 2 + f1(1) = 3 + 2 + 1
所谓不动点，我的理解就是这里的f1 f2 f3 ...就是不动点。（我数学不好，这么理解是否可以请指正）

也就是说，对于任意 x = n，我们都可以找到一个等效的函数fn，比如说 f100 = 100 + 99 + 98 + ... + 1。

绕了一圈回来了，的确用递归算数字求和小题大做。但是这说明了递归可以被展开的事实。

然后我们想，既然 f(x) 可以用 fx(x) 来代替，那么我们可以这么做：给定一个x，我们不用f(x)，而是展开成fn来计算。
比如：
Func<int, int> GetFn(n)
{
  if (n == 1) return x => 1 //注意，当 n = 1 的时候，fn(n) = f(n)，这就是说计算1+2+...+100的函数你拿来1+2+...+10肯定不对了。
  if (n == 2) return x => 1 + 2;
  if (x == 3) return x => 1 + 2 + 3;
  ...
}
调用 int sum = GetFn(n)(n);

你要说了，多么傻的办法，再说 n 也没有个头，你这个造到哪里去。

要是计算机自动能自动构造出一个求和的函数就好了。

重点来了。
我们从API调用者的角度看，我们需要这么一个函数：
输入一个原函数，自动生成一个可以计算n的展开函数（不动点函数）。

顺便说下，这种让计算机自动产生代码的编程方式叫做 meta programming（元编程）。

对于一个 Func<int, int>的原函数，它的自动生成不动点函数的调用可以这么写：

C# code

static Func<T, TReturn> FixedPointCombinator<T, TReturn>(Func<Func<T, TReturn>, Func<T, TReturn>> func)
{
}

怎么解决？
没错，就是这个公式：
fix(F)(n) = F(fix(F))(n) 参考：http://zh.wikipedia.org/wiki/%E4%B8%8D%E5%8A%A8%E7%82%B9%E7%BB%84%E5%90%88%E5%AD%90

C# code

static Func<T, TReturn> FixedPointCombinator<T, TReturn>(Func<Func<T, TReturn>, Func<T, TReturn>> func)
{
    return x => func(FixedPointCombinator(func))(x);
}

函数有了，我们调用下：

C# code

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));            
}

运算结果，5050，正确。

完整的程序：

C# code

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));            
        }
    }
}

再想一想。

一般的递归就是直接调用递归函数，自己调用自己求解。
Fixed Point Combinator，将递归函数作为参数（模板），内部用递归方法构造不动点算子（展开递归函数），最后将对递归的调用转化为对不动点函数的调用，求解。

好了，我写完了，不知道大家理解了没有。其实很简单的。

------解决方案--------------------
我的理解就是一方法套一匿名代理, 很有技巧。。。
------解决方案--------------------