建站
咨詢
售后
建站咨詢
新聞中心
Lambda表達(dá)式實(shí)現(xiàn)遞歸表達(dá)，在.NET編程中具有很重要的意義。遞歸可以更簡(jiǎn)便循環(huán)過程，但這里需要從“偽”遞歸開始談起。
在王益等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場(chǎng)前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站設(shè)計(jì) 網(wǎng)站設(shè)計(jì)制作定制開發(fā),公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計(jì),營(yíng)銷型網(wǎng)站建設(shè),成都外貿(mào)網(wǎng)站制作,王益網(wǎng)站建設(shè)費(fèi)用合理。
其實(shí)這從來(lái)不是一個(gè)很簡(jiǎn)單的事情，雖然有些朋友認(rèn)為這很簡(jiǎn)單。
“偽”遞歸
例如，我們想要使用Lambda表達(dá)式編寫一個(gè)計(jì)算遞歸的fac函數(shù)，一開始我們總會(huì)設(shè)法這樣做：
- Func fac = x => x <= 1 ? 1 : x * fac(x - 1);
不過此時(shí)編譯器會(huì)無(wú)情地告訴我們，fac還沒有定義。于是您可能會(huì)想，這個(gè)簡(jiǎn)單，分兩行寫咯。于是有朋友就會(huì)給出這樣的代碼：
- Func fac = null;
- fac = x => x <= 1 ? 1 : x * fac(x - 1);
這樣看起來(lái)也很“遞歸”，執(zhí)行起來(lái)似乎也沒有問題。但是，其實(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á)式寫遞歸“從來(lái)不是一個(gè)很簡(jiǎn)單的事情”。那么這個(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ì)象。請(qǐng)注意，這里是根據(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á)式來(lái)構(gòu)造一個(gè)遞歸函數(shù)”的難點(diǎn)是因?yàn)椤拔覀冋跇?gòu)造的東西是沒有名字的”，因此“我們無(wú)法調(diào)用自身”。那么，如果我們換種寫法，把我們正在調(diào)用的匿名函數(shù)作為參數(shù)傳給自己，那么不就可以在匿名函數(shù)的方法體中，通過調(diào)用參數(shù)來(lái)調(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);
請(qǐng)注意，這里的f參數(shù)是一個(gè)函數(shù)，它也是我們正在使用Lambda表達(dá)式定義的匿名委托（就是“(f, x) => ...”這一長(zhǎng)串）。為了遞歸調(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)去。于是我們可以這樣來(lái)獲得階乘的結(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));
用腦袋的話來(lái)說，F(xiàn)ix方法應(yīng)該被視為是內(nèi)置方法。您比較Fix方法內(nèi)部和之前的Make方法內(nèi)部的寫法，就能夠意識(shí)到兩種做法之間的差距了。
由于我的腦袋不如裝配腦袋的腦袋裝配的那么好，即使看來(lái)一些推導(dǎo)過程之后還是無(wú)法做到100%的理解，我還需要閱讀更多的內(nèi)容。希望在以后的某一天，我可以把這部分內(nèi)容融會(huì)貫通地理解下來(lái)，并且可以詳細(xì)地解釋給大家聽。在這之前，我還是聽腦袋的話，把Fix強(qiáng)行記在腦袋里吧。
***，希望大家多多參與一些如“函數(shù)式鏈表快速排序”這樣的趣味編程——不過，千萬(wàn)不要學(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)然，偶爾玩玩是有益無(wú)害的。
本文來(lái)自趙劼的博客園文章《使用Lambda表達(dá)式編寫遞歸函數(shù)》
【編輯推薦】
- .NET Lambda表達(dá)式的函數(shù)式特性：索引示例
- .NET Lambda表達(dá)式的語(yǔ)義：字符串列表范例
- 使用.NET 3.5 Lambda表達(dá)式實(shí)現(xiàn)委托
- 各版本.NET委托的寫法回顧
- C# Actor模型開發(fā)實(shí)例：網(wǎng)絡(luò)爬蟲
當(dāng)前題目：使用Lambda表達(dá)式編寫遞歸函數(shù)
分享鏈接：http://www.5511xx.com/article/ccohicd.html
