Lambda表達(dá)式實(shí)現(xiàn)遞歸表達(dá)，在.NET編程中具有很重要的意義。遞歸可以更簡便循環(huán)過程，但這里需要從“偽”遞歸開始談起。

其實(shí)這從來不是一個(gè)很簡單的事情，雖然有些朋友認(rèn)為這很簡單。

“偽”遞歸

例如，我們想要使用Lambda表達(dá)式編寫一個(gè)計(jì)算遞歸的fac函數(shù)，一開始我們總會(huì)設(shè)法這樣做：

Func fac = x => x <= 1 ? 1 : x * fac(x - 1); 

不過此時(shí)編譯器會(huì)無情地告訴我們，fac還沒有定義。于是您可能會(huì)想，這個(gè)簡單，分兩行寫咯。于是有朋友就會(huì)給出這樣的代碼：

Func fac = null;  
fac = x => x <= 1 ? 1 : x * fac(x - 1); 

這樣看起來也很“遞歸”，執(zhí)行起來似乎也沒有問題。但是，其實(shí)這并沒有使用Lambda表達(dá)式構(gòu)造一個(gè)遞歸函數(shù)，為什么呢？因?yàn)槲覀兪褂肔ambda表達(dá)式構(gòu)造的其實(shí)只是一個(gè)普通的匿名方法，它是這樣的：

x => x <= 1 ? 1 : x * fac(x - 1); 

既然是“匿名方法”，這個(gè)構(gòu)造的東西是沒有名字的——因此用Lambda表達(dá)式寫遞歸“從來不是一個(gè)很簡單的事情”。那么這個(gè)Lambda表達(dá)式里的fac是什么呢？是一個(gè)“委托”。因此，這只是個(gè)“調(diào)用了一個(gè)委托”的Lambda表達(dá)式?！拔袑?duì)象”和“匿名方法”是有區(qū)別的，前者是一個(gè)實(shí)際的對(duì)象，而后者只是個(gè)“定義方式”，只是“委托對(duì)象”可以成為“匿名方法”的載體而已。這個(gè)Lambda表達(dá)式構(gòu)造的“委托對(duì)象”在調(diào)用時(shí)，它會(huì)去尋找fac這個(gè)引用所指向的委托對(duì)象。請注意，這里是根據(jù)“引用”去找“對(duì)象”，這意味著Lambda表達(dá)式構(gòu)造的委托對(duì)象在調(diào)用時(shí)，fac可能已經(jīng)不再指向當(dāng)初的委托對(duì)象了。例如：

Func fac = null;  
fac = x => x <= 1 ? 1 : x * fac(x - 1);  
Console.WriteLine(fac(5)); // 120;  
 
Func facAlias = fac;  
fac = x => x;  
Console.WriteLine(facAlias(5)); // 20 

***次打印出的120是正確的結(jié)果。不過facAlias從fac那里“接過”了使用Lambda表達(dá)式構(gòu)造的委托對(duì)象之后，我們讓fac引用指向了新的匿名方法x => x。于是facAlias在調(diào)用時(shí)：

facAlias(5)     <— facAlias是x => x <= 1 ? 1 : x * fac(x – 1)  
= 5 <= 1 ? 1 : 5 * fac(5 - 1)  
= 5 * fac(4)    <— 注意此時(shí)fac是x => x 
= 5 * 4 
= 20 

自然就不對(duì)了。

因此，使用Lambda表達(dá)式構(gòu)造一個(gè)遞歸函數(shù)不是一件容易的事情。把自己傳給自己吧

可能已經(jīng)有朋友知道“標(biāo)準(zhǔn)”的做法是什么樣的，不過我這里還想談一下我當(dāng)時(shí)遇到這個(gè)問題時(shí)想到的一個(gè)做法。比較笨（非常符合我的特點(diǎn)），但是可以解決問題。

　　我的想法是，既然使用“Lambda表達(dá)式來構(gòu)造一個(gè)遞歸函數(shù)”的難點(diǎn)是因?yàn)椤拔覀冋跇?gòu)造的東西是沒有名字的”，因此“我們無法調(diào)用自身”。那么，如果我們換種寫法，把我們正在調(diào)用的匿名函數(shù)作為參數(shù)傳給自己，那么不就可以在匿名函數(shù)的方法體中，通過調(diào)用參數(shù)來調(diào)用自身了嗎？于是，原本我們構(gòu)造fac方法的Lambda表達(dá)式：

x => x <= 1 ? 1 : x * fac(x - 1); 

就需要變成：

(f, x) => x <= 1 ? 1 : x * f(f, x - 1); 

請注意，這里的f參數(shù)是一個(gè)函數(shù)，它也是我們正在使用Lambda表達(dá)式定義的匿名委托（就是“(f, x) => ...”這一長串）。為了遞歸調(diào)用，它還必須把自身作為***個(gè)參數(shù)傳入下一層的調(diào)用中去，所以***不是fac(x - 1)而是f(f, x - 1)。我們可以把這個(gè)匿名函數(shù)放到一個(gè)叫做selfFac的變量中去：

var selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1); 

在***次調(diào)用selfFac時(shí)，我們必須把它自身傳遞進(jìn)去。于是我們可以這樣來獲得階乘的結(jié)果：

Console.WriteLine(selfFac(selfFac, 5)); // 120; 

但是這段代碼沒法編譯通過，因?yàn)榫幾g器不知道selfFac應(yīng)該是什么類型的委托對(duì)象。不過根據(jù)selfFac(selfFac, 5)的調(diào)用方式，我們可以推斷出，這個(gè)委托類型會(huì)接受兩個(gè)參數(shù)，***個(gè)是它自身的類型，第二個(gè)是個(gè)整型，而返回的也是個(gè)整型。于是，我們可以得出委托的簽名了：

delegate int SelfFactorial(SelfFactorial selfFac, int x); 

哎，但是這一點(diǎn)都不通用啊。沒關(guān)系，我們可以寫的通用一些：

delegate TResult SelfApplicable(SelfApplicable self, T arg); 

這樣，我們便可以定義selfFac，甚至于selfFib（菲波納契數(shù)列）：

SelfApplicable selfFib = (f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2);  
Console.WriteLine(selfFib(selfFib, 5)); // 8 

但是，這還不是我們所需要的遞歸函數(shù)啊。沒錯(cuò)，我們需要的是傳入一個(gè)x就可以得到結(jié)果的函數(shù)，這種每次還需要把自己傳進(jìn)去的東西算什么？不過這個(gè)倒也容易，在selfXxx的基礎(chǔ)上再前進(jìn)一步就可以了：

SelfApplicable selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1);  
Func fac = x => selfFac(selfFac, x);  
 
SelfApplicable selfFib = (f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2);  
Func fib = x => selfFib(selfFib, x); 

為此，我們甚至可以總結(jié)出一個(gè)輔助方法：

static Func Make(SelfApplicable self)  
{  
    return x => self(self, x);  
}　　于是乎：  
 
var fac = Make((f, x) => x <= 1 ? 1 : x * f(f, x - 1));  
var fib = Make((f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2)); 

這樣我們便使用Lambda表達(dá)式定義了遞歸函數(shù)。當(dāng)然，需要兩個(gè)參數(shù)的遞歸函數(shù)定義方式也比較類似。首先是SelfApplicable委托類型和對(duì)應(yīng)的輔助方法：

// 委托類型  
delegate TResult SelfApplicable(SelfApplicable self, T1 arg1, T2 arg2);  
 
// 輔助方法  
static Func Make(SelfApplicable self)  
{  
    return (x, y) => self(self, x, y);  
}　　于是使用“輾轉(zhuǎn)相除法”計(jì)算***公約數(shù)的gcd函數(shù)便是：  
 
var gcd = Make((f, x, y) => y == 0 ? x : f(f, y, x % y));  
Console.WriteLine(gcd(20, 36)); // 4 

這也是我目前憑“個(gè)人能力”能夠走出的最遠(yuǎn)距離了。

不動(dòng)點(diǎn)組合子

但是裝配腦袋很早給了我們更好的解決方法：

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

Fix求出的是函數(shù)f的不動(dòng)點(diǎn)，它就是我們所需要的遞歸函數(shù)：

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

用腦袋的話來說，F(xiàn)ix方法應(yīng)該被視為是內(nèi)置方法。您比較Fix方法內(nèi)部和之前的Make方法內(nèi)部的寫法，就能夠意識(shí)到兩種做法之間的差距了。

由于我的腦袋不如裝配腦袋的腦袋裝配的那么好，即使看來一些推導(dǎo)過程之后還是無法做到100%的理解，我還需要閱讀更多的內(nèi)容。希望在以后的某一天，我可以把這部分內(nèi)容融會(huì)貫通地理解下來，并且可以詳細(xì)地解釋給大家聽。在這之前，我還是聽腦袋的話，把Fix強(qiáng)行記在腦袋里吧。

***，希望大家多多參與一些如“函數(shù)式鏈表快速排序”這樣的趣味編程——不過，千萬不要學(xué)腦袋這樣做：

var qsort = Fix, IEnumerable>(f => l => 
l.Any() ? f(l.Skip(1).Where(e => e < l.First())).Concat(Enumerable.Repeat(l.First(), 1)).Concat(f(l.Skip(1).Where(e => e >= l.First()))) : Enumerable.Empty()); 

當(dāng)然，偶爾玩玩是有益無害的。

本文來自趙劼的博客園文章《使用Lambda表達(dá)式編寫遞歸函數(shù)》

【編輯推薦】

1. .NET Lambda表達(dá)式的函數(shù)式特性：索引示例
2. .NET Lambda表達(dá)式的語義：字符串列表范例
3. 使用.NET 3.5 Lambda表達(dá)式實(shí)現(xiàn)委托
4. 各版本.NET委托的寫法回顧
5. C# Actor模型開發(fā)實(shí)例：網(wǎng)絡(luò)爬蟲