艾伟_转载：使用Lambda表达式编写递归函数

前言

著名的牛顿同学曾经说过：如果说我比别人看得更远些,那是因为我站在了巨人的肩上.

原文：If I have been able to see further, it was only because I stood on the shoulders of giants.

What's Lambda表达式?

请参考msdn：Lambda 表达式（C# 编程指南）

Lambda表达式编写递归函数? How?

建议没有看过老赵的《使用Lambda表达式编写递归函数》这篇文章的朋友，请先前往围观，你会受益匪浅。

原文实现如下的递归效果：

var fac = Fix<int, int>(f => x => x <= 1 ? 1 : x * f(x - 1));
var fib = Fix<int, int>(f => x => x <= 1 ? 1 : f(x - 1) + f(x - 2));
var gcd = Fix<int, int, int>(f => (x, y) => y == 0 ? x : f(y, x % y));

颇有意思，能够把递归发挥到这种极致。更有意思的是Fix这个简短而又神秘莫测的方法：

static Func Fix(Func<Func, Func> f)
{
    return x => f(Fix(f))(x);
}
static Func Fix(Func<Func, Func> f)
{
    return (x, y) => f(Fix(f))(x, y);
}

Oh my god! 这是人类写的代码吗？

据原文介绍，此得意之作是装配脑袋的脑袋想出来的。至于有兴趣且希望前往一窥究竟的朋友，我先给大家打个预防针——首先选择你一天中最清醒的时候，最好带上氧气瓶，以防由于其大师级的文章而可能造成短暂性的脑缺氧...

（装配脑袋的两篇大师级文章：1. VS2008亮点：用Lambda表达式进行函数式编程 和 2. 用Lambda表达式进行函数式编程（续）：用C#实现Y组合子）

人在江湖，高手如云。葵花宝典，如来神掌，此乃上乘武功，高手行走江湖的必杀技。我等后辈，深知神功非一日可练就，日夜苦练。幸好鄙人天资聪慧，一日秋高气爽，幸见两位大师切磋比试，深得大师真传，练就“抛砖引玉”神功，我抛，我抛！——大家请接好 -.-!

抛的是什么砖？

前面由Lambda表达式使出的一招函数式编程，经润色成递归函数，犹如手握屠龙刀一般登峰造极；今日我略懂窍门，奉上倚天剑，与屠龙刀集一身，可谓无懈可击。

大家发现前面实现的3个递归函数有什么共同点吗？没错，都是有返回值的。因为 Fix 返回的是 Func 或 Func 类型，换句话说 TResult 就是递归结束后期望返回的类型。如果是无返回值的递归呢？好的，聪明的你此刻应该知道又是Action 出场了。

没错，我们要做的事情就是让 Fix 返回 Action 。当然，和前面的不一般的 Func 一样， Action 也不是等闲之辈。

x => f(Fix(f))(x)

是的，我一不小心写了一个(实际上是照葫芦画瓢)：

public static Action Fix(Func<Action, Action> f)
{
    return x => f(Fix(f))(x);
}
public static Action Fix(Func<Action, Action> f)
{
    return (x, y) => f(Fix(f))(x, y);
}

好的，在你还没被以上代码弄晕之前，我先举一个大家都熟悉的例子——二叉树遍历 （二叉树是我大学时学数据结构最感兴趣的一部分，另一个感兴趣的是教我数据结构的女老师）

先来回顾一下二叉树的一般递归算法，如中序遍历算法可用经典的C语言描述为：

void InOrder(BinTree T)
{ 
    if(T)// 如果二叉树非空
   { 
        InOrder(T->lchild)；
        printf("％c"，T->data)； // 访问结点
        InOrder(T->rchild);
     }
} // InOrder

（题外话：想当年我用C语言费了多少时间不断写二叉树的结构和遍历，请注意不是照搬书本的代码。多少次内存溢出，多少次与指针作斗争，了解，忘记，再了解，又忘记，... 现在如果让我来用C语言写二叉树遍历，可能写出的代码会把编译器吓跑，嘿嘿。何况，此宝地乃.Net 牛人的汇集之地，更何况我想写的是泛型二叉树）

泛型二叉树

class Node
{
    public T Value { get; set; }
    public Node Left { get; set; }
    public Node Right { get; set; }
    public Node()
    { }
    public Node(T value)
        : this(value, null, null)
    { }
    public Node(T value, T left, T right)
        : this(value, new Node(left), new Node(right))
    { }
    public Node(T value, Node left, Node right)
    {
        Value = value;
        Left = left;
        Right = right;
    }
}

老实说，在实现手动构造二叉树时，我不知道如何写尽量少的代码并且这些代码还要能够清晰反映树的结构。为此我唯一想到的是类似XElement那样，它写出的代码是树形的，让人从代码可以联想到对象的结构。

现在，我们试着用 Node 来构造以下的二叉树：

        /*
    建立一棵简单的二叉树：
     A
    / \
   B  C
  /   / \
 D  E   F
         */
static Node<char> BuildTree()
{
    return new Node<char>('A',
                new Node<char>('B',
                    new Node<char>('D'), null),
                new Node<char>('C', 
                    'E', 'F'));
}

（以上代码始终不够理想，too many Node，期待更好的构造二叉树写法）

请原谅我带大家兜了一圈花园，现在回到刚才的非人类写的代码：

public static Action Fix(Func<Action, Action> f)
{
    return x => f(Fix(f))(x);
}

结合刚才的二叉树，现在装配以上代码来实现对二叉树的三种遍历——中序，先序和后序

var inorder = Fix<Node<char>>(f=> n => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } });
var preorder = Fix<Node<char>>(f=> n => { if (n != null) { Console.Write(n.Value); f(n.Left); f(n.Right); } });
var postorder = Fix<Node<char>>(f=> n => { if (n != null) { f(n.Left); f(n.Right); Console.Write(n.Value); } });
Node<char> tree = BuildTree();
Console.WriteLine("（1） 中序序列（inorder traversal）");
inorder(tree);
Console.WriteLine();
Console.WriteLine("（2） 先序序列（preorder traversal）");
preorder(tree);
Console.WriteLine();
Console.WriteLine("（3） 后序序列（postorder traversal）");
postorder(tree);
Console.WriteLine();

运行后的效果：

（大家可以在脑里对结果进行验证一下，或点此查看）

其实以上代码的关键部分f => n => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } } 跟我们的思维还是类似的。如果你不习惯这种写法，也可以写成多行的形式：

f =>
    n =>
    {
        if (n != null)
        {
            f(n.Left);
            Console.Write(n.Value);
            f(n.Right);
        }
    });

f 是 Action 类型，可以理解为将要实现递归的委托；

n 是 T类型，在本文它是 Node<char> 类型，是当前遍历的节点。

f(n.Left) 和 f(n.Right) 也就很好理解了，就是访问左右节点。

多参数

对于多参数的情况，如 f => (arg1, arg2) =>{ ... } ，虽然上述方法也可以“凑合”着用，例如可以改成单参数的形式：

object arg2; f => arg1 =>{use arg2 to do sth... }

但是这样一来，其中一个弊端就是f => arg1 =>{use arg2 to do sth... }不能单独抽取出来进行复用，意味着它的使用范围变窄了。因为如刚才的中序遍历，并不一定在方法里构造相应的委托，大可“搬”到方法外面去。

例如：

var inorder = Fix<Node<char>>(...);

“搬”出去以后：

public  static Action<Node<char>> inorder = Fix<Node<char>>(...);

因此，完全有必要重载 Fix 方法提供多参数的形式。

文章开端已经列出了2个参数的重载方法：

public static Action Fix(Func<Action, Action> f)
{
    return (x, y) => f(Fix(f))(x, y);
}

现在使用上述方法来写一个递归遍历指定目录的所有子目录，并记录这些目录到一个List 对象里：

var traversal_help = Fix<string, List<string>>(f => (current, pathList) =>
{
    //添加当前目录到pathList
    pathList.Add(current);
    //访问当前目录的文件夹
    foreach (string path in Directory.GetDirectories(current))
    {
        //递归调用
        f(path, pathList);
    }
});
List<string> result = new List<string>();
traversal_help("C:\\", result);

重载 (纯Action版)

x => f(Fix(f), x)

Oh my god! 又是非人类写的代码？

是的，我又一不小心写了另外一个版本：

public static Action Fix(Action<Action, T> f)
{
    return x => f(Fix(f), x);
}
static Action Fix(Action<Action, T1, T2> f)
{
    return (x, y) => f(Fix(f), x, y);
}

以上两个方法已经彻底见不到 Func 的踪影了，我谓之为“纯Action”版，跟前一个版本同样是实现无返回值的递归调用。

使用上也极其简单，这里还是拿二叉树遍历来说明：

var inorder = Fix<Node<char>>((f, n) => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } });
var preorder = Fix<Node<char>>((f, n) => { if (n != null) { Console.Write(n.Value); f(n.Left); f(n.Right); } });
var postorder = Fix<Node<char>>((f, n) => { if (n != null) { f(n.Left); f(n.Right); Console.Write(n.Value); } });

这种写法其实跟前一种写法只有很小的差别：

f => n => ... 写成：(f, n) => ...

同理，多参数的情况:

f => (n1, n2) => ... 写成：(f, n1, n2) => ...

没错，如此而已。这里我想问问大家更乐于使用哪种写法呢？

性能比较

两个版本在性能上区别会不会有很大区别？

使用计时器 CodeTimer ，测试代码：

var inorder1 = Fix<Node<char>>(f => n => { if (n != null) { f(n.Left); f(n.Right); } });
var inorder2 = Fix<Node<char>>((f, n) => { if (n != null) { f(n.Left); f(n.Right); } });
Node<char> tree = BuildTree();
CodeTimer.Initialize();
new List<int> { 10000, 100000, 1000000 }.ForEach(n =>
{
    CodeTimer.Time("Fix v1 * " + n, n, () => inorder1(tree));
    CodeTimer.Time("Fix v2 * " + n, n, () => inorder2(tree));
});

测试代码其实就是二叉树中序遍历，只是打印节点的语句被去掉（即去掉 Console.Write(n.Value) ）。

两个版本分别执行一万，十万及一百万次，得到的测试结果是：

Fix v1 * 10000
        Time Elapsed:   413ms
        CPU Cycles:     897,224,108
        Gen 0:          10
        Gen 1:          0
        Gen 2:          0

Fix v2 * 10000
        Time Elapsed:   308ms
        CPU Cycles:     671,960,256
        Gen 0:          5
        Gen 1:          0
        Gen 2:          0

Fix v1 * 100000
        Time Elapsed:   3,118ms
        CPU Cycles:     6,796,717,873
        Gen 0:          109
        Gen 1:          0
        Gen 2:          0

Fix v2 * 100000
        Time Elapsed:   3,061ms
        CPU Cycles:     6,680,823,182
        Gen 0:          54
        Gen 1:          1
        Gen 2:          0

Fix v1 * 1000000
        Time Elapsed:   31,358ms
        CPU Cycles:     67,992,085,293
        Gen 0:          1090
        Gen 1:          3
        Gen 2:          0

Fix v2 * 1000000
        Time Elapsed:   31,576ms
        CPU Cycles:     68,836,391,613
        Gen 0:          545
        Gen 1:          3
        Gen 2:          0

结果显示两个版本在速度上旗鼓相当，而“纯Action”版在GC上优于前者。

多参数的VS智能提示问题

上述代码从理论上和实际上来说都是没问题的。但是作为这篇文章的作者，我必须要很负责任的告诉大家，无论哪个Fix版本，对于多参数的情况，VS智能提示令我感到很意外，甚至无法理解。 而且更令我抓不着头脑的是，这些VS智能提示并不是完全“瘫痪”，而是时而行，时而丢失，好像在跟你玩捉迷藏那样。我所见到的有以下两种情况：

1. 类型推断正确，但智能提示丢失

虽然 VS 对类型的推断是正确的：

（看后面 f 的类型够吓人的）

但当你接着编写 pathList 时，VS就判断成未知类型：

然后当写完整个pathList后，点不到任何方法出来。此时对于VS来说，这个pathList相当于是凭空捏造的那样。

于是硬着头皮写完Add方法后，把鼠标移上去，提示信息又能够跑出来了。

这时候跑回pathList后点方法，智能提示才跑出来，但对于编程人员来说已经没有用了，因为整个方法都已经写完了。

但当你再次写pathList还是判断成未知类型，无语。

2. 类型推断令人费解

在foreach语句前写 f ，VS的智能提示是正确的，即 Action>

到了foreach里面写 f ，你猜猜变成了什么，竟然是 Func>

由于以上例子递归调用是放在foreach里面，所以必须在foreach里面写f，于是再次硬着头皮写完整句代码，提示信息再一次“回个神来”。

（注：我的编程环境是win7（中文）+VS2008（英文）+SP1）

这莫非是VS2008的一个bug？有意思吧，大家不妨把以上代码放到自己的VS里试试，看看是否只有我的VS才这样。

如果大家的VS对以上代码的智能提示都是乱糟的，那么我建议认识微软的朋友高举此文，游行到微软的大门，嘿嘿。

末了说一句，以上代码在VS2010中的智能提示是Perfect的。VS2010真是很好很强大，唯一不爽的就是逼得我要换机器，可怜我的NoteBook刚买不久 TT。

结语

其实我还想兴致勃勃的看看 x => f(Fix(f), x) 在没有 Lambda 表达式和匿名函数的支持会是什么模样，以一窥其真谛帮助理解，但用Reflector 反编译以后得到的是以下代码，... 不是我能看懂的东西，作罢...

    
public static Action Fix(Action, T> f)
{
    <>c__DisplayClass7 CS$<>8__locals8;
    Action CS$1$0000;
    CS$<>8__locals8 = new <>c__DisplayClass7();
    CS$<>8__locals8.f = f;
    CS$1$0000 = new Action(CS$<>8__locals8.b__6);
Label_001D:
    return CS$1$0000;
}

请懂得以上代码含义的朋友说说。

至于较早关于Lambda表达式和递归编程结合的博文可能要追溯到这位老外的文章了：

Recursive lambda expressions (从Post时间来看是2007年5月11日)