我們將介紹的是如何使用Lambda表達式編寫遞歸函數(shù)，這些代碼有很多人認為跟天書無異，但是我們還是能從中看出一些端倪來。

前言

著名的牛頓同學曾經(jīng)說過：如果說我比別人看得更遠些,那是因為我站在了巨人的肩上.

原文：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表達式編寫遞歸函數(shù)? How?

建議沒有看過老趙的《使用Lambda表達式編寫遞歸函數(shù)》這篇文章的朋友，請先前往圍觀，你會受益匪淺。

原文實現(xiàn)如下的遞歸效果：

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

頗有意思，能夠把遞歸發(fā)揮到這種***。更有意思的是Fix這個簡短而又神秘莫測的方法：

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

Oh my god! 這是人類寫的代碼嗎？

據(jù)原文介紹，此得意之作是裝配腦袋的腦袋想出來的。至于有興趣且希望前往一窺究竟的朋友，我先給大家打個預防針——首先選擇你一天中最清醒的時候，***帶上氧氣瓶，以防由于其大師級的文章而可能造成短暫性的腦缺氧 ...

（裝配腦袋的兩篇大師級文章：1. VS2008亮點：用Lambda表達式進行函數(shù)式編程 和 2. 用Lambda表達式進行函數(shù)式編程（續(xù)）：用C#實現(xiàn)Y組合子）

人在江湖，高手如云?？▽毜?，如來神掌，此乃上乘武功，高手行走江湖的必殺技。我等后輩，深知神功非一日可練就，日夜苦練。幸好鄙人天資聰慧，一日秋高氣爽，幸見兩位大師切磋比試，深得大師真?zhèn)?，練就“拋磚引玉”神功，我拋，我拋！——大家請接好 -.-!

拋的是什么磚？

前面由Lambda表達式使出的一招函數(shù)式編程，經(jīng)潤色成遞歸函數(shù)，猶如手握屠龍刀一般登峰造極；今日我略懂竅門，奉上倚天劍，與屠龍刀集一身，可謂無懈可擊。

大家發(fā)現(xiàn)前面實現(xiàn)的3個遞歸函數(shù)有什么共同點嗎？沒錯，都是有返回值的。因為 Fix 返回的是 Func 或 Func 類型，換句話說 TResult 就是遞歸結束后期望返回的類型。如果是無返回值的遞歸呢？好的，聰明的你此刻應該知道又是Action 出場了。

沒錯，我們要做的事情就是讓 Fix 返回 Action 。當然，和前面的不一般的 Func 一樣， Action 也不是等閑之輩。

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

是的，我一不小心寫了一個(實際上是照葫蘆畫瓢)：

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

好的，在你還沒被以上代碼弄暈之前，我先舉一個大家都熟悉的例子——二叉樹遍歷 （二叉樹是我大學時學數(shù)據(jù)結構最感興趣的一部分，另一個感興趣的是教我數(shù)據(jù)結構的女老師）

先來回顧一下二叉樹的一般遞歸算法，如中序遍歷算法可用經(jīng)典的C語言描述為：

void InOrder(BinTree T)  
{   
    if(T)// 如果二叉樹非空  
   {   
        InOrder(T->lchild)；  
 
        printf("％c"，T->data)； // 訪問結點  
 
        InOrder(T->rchild);  
     }  
} // InOrder 

（題外話：想當年我用C語言費了多少時間不斷寫二叉樹的結構和遍歷，請注意不是照搬書本的代碼。多少次內(nèi)存溢出，多少次與指針作斗爭，了解，忘記，再了解，又忘記，... 現(xiàn)在如果讓我來用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;  
    }  
} 

老實說，在實現(xiàn)手動構造二叉樹時，我不知道如何寫盡量少的代碼并且這些代碼還要能夠清晰反映樹的結構。為此我唯一想到的是類似XElement那樣，它寫出的代碼是樹形的，讓人從代碼可以聯(lián)想到對象的結構。

現(xiàn)在，我們試著用 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，期待更好的構造二叉樹寫法）

請原諒我?guī)Т蠹叶盗艘蝗▓@，現(xiàn)在回到剛才的非人類寫的代碼：

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

結合剛才的二叉樹，現(xiàn)在裝配以上代碼來實現(xiàn)對二叉樹的三種遍歷——中序，先序和后序

var inorder = Fixchar>>(f=> n => { if (n != null) { f(n.Left); Console.Write(n.Value); f(n.Right); } });  
var preorder = Fixchar>>(f=> n => { if (n != null) { Console.Write(n.Value); f(n.Left); f(n.Right); } });  
var postorder = Fixchar>>(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 類型，可以理解為將要實現(xiàn)遞歸的委托；

n 是 T類型，在本文它是 Node 類型，是當前遍歷的節(jié)點。

f(n.Left) 和 f(n.Right) 也就很好理解了，就是訪問左右節(jié)點。

多參數(shù)

對于多參數(shù)的情況，如 f => (arg1, arg2) =>{ ... } ，雖然上述方法也可以“湊合”著用，例如可以改成單參數(shù)的形式：

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

但是這樣一來，其中一個弊端就是f => arg1 =>{use arg2 to do sth... }不能單獨抽取出來進行復用，意味著它的使用范圍變窄了。因為如剛才的中序遍歷，并不一定在方法里構造相應的委托，大可“搬”到方法外面去。

例如：

var inorder = Fixchar>>(...); 

“搬”出去以后：

public  static Actionchar>> inorder = Fixchar>>(...); 

因此，完全有必要重載 Fix 方法提供多參數(shù)的形式。

文章開端已經(jīng)列出了2個參數(shù)的重載方法：

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

現(xiàn)在使用上述方法來寫一個遞歸遍歷指定目錄的所有子目錄，并記錄這些目錄到一個List 對象里：

var traversal_help = Fix<string, List<string>>(f => (current, pathList) =>  
{  
    //添加當前目錄到pathList  
    pathList.Add(current);  
    //訪問當前目錄的文件夾  
    foreach (string path in Directory.GetDirectories(current))  
    {  
        //遞歸調(diào)用  
        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, T> f)  
{  
    return x => f(Fix(f), x);  
}  
 
static Action Fix(Action, T1, T2> f)  
{  
    return (x, y) => f(Fix(f), x, y);  
} 

以上兩個方法已經(jīng)徹底見不到 Func 的蹤影了，我謂之為“純Action”版，跟前一個版本同樣是實現(xiàn)無返回值的遞歸調(diào)用。

使用上也極其簡單，這里還是拿二叉樹遍歷來說明：

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

這種寫法其實跟前一種寫法只有很小的差別：

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

同理，多參數(shù)的情況:

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

沒錯，如此而已。這里我想問問大家更樂于使用哪種寫法呢？

性能比較

兩個版本在性能上區(qū)別會不會有很大區(qū)別？

使用計時器 CodeTimer ，測試代碼：

var inorder1 = Fixchar>>(f => n => { if (n != null) { f(n.Left); f(n.Right); } });  
var inorder2 = Fixchar>>((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));  
}); 

測試代碼其實就是二叉樹中序遍歷，只是打印節(jié)點的語句被去掉（即去掉 Console.Write(n.Value) ）。

兩個版本分別執(zhí)行一萬，十萬及一百萬次，得到的測試結果是：

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上優(yōu)于前者。

多參數(shù)的VS智能提示問題

上述代碼從理論上和實際上來說都是沒問題的。但是作為這篇文章的作者，我必須要很負責任的告訴大家，無論哪個Fix版本，對于多參數(shù)的情況，VS智能提示令我感到很意外，甚至無法理解。 而且更令我抓不著頭腦的是，這些VS智能提示并不是完全“癱瘓”，而是時而行，時而丟失，好像在跟你玩捉迷藏那樣。我所見到的有以下兩種情況：

1. 類型推斷正確，但智能提示丟失

雖然Visual Studio對類型的推斷是正確的：

[[6248]]

（看后面 f 的類型夠嚇人的）

但當你接著編寫 pathList 時，Visual Studio就判斷成未知類型：

然后當寫完整個pathList后，點不到任何方法出來。此時對于VS來說，這個pathList相當于是憑空捏造的那樣。

于是硬著頭皮寫完Add方法后，把鼠標移上去，提示信息又能夠跑出來了。

[[6249]]

這時候跑回pathList后點方法，智能提示才跑出來，但對于編程人員來說已經(jīng)沒有用了，因為整個方法都已經(jīng)寫完了。

但當你再次寫pathList還是判斷成未知類型，無語。

 

2. 類型推斷令人費解

在foreach語句前寫 f ，VS的智能提示是正確的，即 Action>

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

由于以上例子遞歸調(diào)用是放在foreach里面，所以必須在foreach里面寫f，于是再次硬著頭皮寫完整句代碼，提示信息再一次“回個神來”。

（注：我的編程環(huán)境是win7（中文）+VS2008（英文）+SP1）

這莫非是VS2008的一個bug？有意思吧，大家不妨把以上代碼放到自己的VS里試試，看看是否只有我的VS才這樣。

如果大家的VS對以上代碼的智能提示都是亂糟的，那么我建議認識微軟的朋友高舉此文，游行到微軟的大門，嘿嘿。

末了說一句，以上代碼在VS2010中的智能提示是Perfect的。Visual Studio 2010真是很好很強大，唯一不舒服的就是逼得我要換機器，可憐我的NoteBook剛買不久 TT。

結語

其實我還想興致勃勃的看看 x => f(Fix(f), x) 在沒有 Lambda 表達式和匿名函數(shù)的支持會是什么模樣，以一窺其真諦幫助理解，但用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日)

原文標題：使用Lambda表達式編寫遞歸函數(shù)（倚天篇）

鏈接：http://www.cnblogs.com/coolcode/archive/2009/10/12/Fix.html

【編輯推薦】

1. Lambda表達式：要性能還是要清晰的代碼？
2. .NET Lambda表達式的函數(shù)式特性：索引示例
3. .NET Lambda表達式的語義：字符串列表范例
4. 使用.NET 3.5 Lambda表達式實現(xiàn)委托
5. 各版本.NET委托的寫法回顧