使用Lambda表達式編寫遞歸函數
其實這從來不是一個很簡單的事情，雖然有些朋友認為這很簡單。
“偽”遞歸
例如，我們想要使用Lambda表達式編寫一個計算遞歸的fac函數，一開始我們總會設法這樣做：
- Func fac = x => x <= 1 ? 1 : x * fac(x - 1);
不過此時編譯器會無情地告訴我們，fac還沒有定義。于是您可能會想，這個簡單，分兩行寫咯。于是有朋友就會給出這樣的代碼：
- Func fac = null;
- fac = x => x <= 1 ? 1 : x * fac(x - 1);
這樣看起來也很“遞歸”，執行起來似乎也沒有問題。但是，其實這并沒有使用Lambda表達式構造一個遞歸函數，為什么呢？因為我們使用Lambda表達式構造的其實只是一個普通的匿名方法，它是這樣的：
- x => x <= 1 ? 1 : x * fac(x - 1);
既然是“匿名方法”，這個構造的東西是沒有名字的——因此用Lambda表達式寫遞歸“從來不是一個很簡單的事情”。那么這個Lambda表達式里的fac是什么呢？是一個“委托”。因此，這只是個“調用了一個委托”的Lambda表達式。“委托對象”和“匿名方法”是有區別的，前者是一個實際的對象，而后者只是個“定義方式”，只是“委托對象”可以成為“匿名方法”的載體而已。這個Lambda表達式構造的“委托對象”在調用時，它會去尋找fac這個引用所指向的委托對象。請注意，這里是根據“引用”去找“對象”，這意味著Lambda表達式構造的委托對象在調用時，fac可能已經不再指向當初的委托對象了。例如：
- 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是正確的結果。不過facAlias從fac那里“接過”了使用Lambda表達式構造的委托對象之后，我們讓fac引用指向了新的匿名方法x => x。于是facAlias在調用時：
- facAlias(5) <— facAlias是x => x <= 1 ? 1 : x * fac(x – 1)
- = 5 <= 1 ? 1 : 5 * fac(5 - 1)
- = 5 * fac(4) <— 注意此時fac是x => x
- = 5 * 4
- = 20
自然就不對了。
因此，使用Lambda表達式構造一個遞歸函數不是一件容易的事情。把自己傳給自己吧
可能已經有朋友知道“標準”的做法是什么樣的，不過我這里還想談一下我當時遇到這個問題時想到的一個做法。比較笨（非常符合我的特點），但是可以解決問題。
我的想法是，既然使用“Lambda表達式來構造一個遞歸函數”的難點是因為“我們正在構造的東西是沒有名字的”，因此“我們無法調用自身”。那么，如果我們換種寫法，把我們正在調用的匿名函數作為參數傳給自己，那么不就可以在匿名函數的方法體中，通過調用參數來調用自身了嗎？于是，原本我們構造fac方法的Lambda表達式：
- x => x <= 1 ? 1 : x * fac(x - 1);
就需要變成：
- (f, x) => x <= 1 ? 1 : x * f(f, x - 1);
請注意，這里的f參數是一個函數，它也是我們正在使用Lambda表達式定義的匿名委托（就是“(f, x) => ...”這一長串）。為了遞歸調用，它還必須把自身作為***個參數傳入下一層的調用中去，所以***不是fac(x - 1)而是f(f, x - 1)。我們可以把這個匿名函數放到一個叫做selfFac的變量中去：
- var selfFac = (f, x) => x <= 1 ? 1 : x * f(f, x - 1);
在***次調用selfFac時，我們必須把它自身傳遞進去。于是我們可以這樣來獲得階乘的結果：
- Console.WriteLine(selfFac(selfFac, 5)); // 120;
但是這段代碼沒法編譯通過，因為編譯器不知道selfFac應該是什么類型的委托對象。不過根據selfFac(selfFac, 5)的調用方式，我們可以推斷出，這個委托類型會接受兩個參數，***個是它自身的類型，第二個是個整型，而返回的也是個整型。于是，我們可以得出委托的簽名了：
- delegate int SelfFactorial(SelfFactorial selfFac, int x);
哎，但是這一點都不通用啊。沒關系，我們可以寫的通用一些：
- delegate TResult SelfApplicable(SelfApplicable self, T arg);
這樣，我們便可以定義selfFac，甚至于selfFib（菲波納契數列）：
- SelfApplicable selfFib = (f, x) => x <= 1 ? 1 : f(f, x - 1) + f(f, x - 2);
- Console.WriteLine(selfFib(selfFib, 5)); // 8
但是，這還不是我們所需要的遞歸函數啊。沒錯，我們需要的是傳入一個x就可以得到結果的函數，這種每次還需要把自己傳進去的東西算什么？不過這個倒也容易，在selfXxx的基礎上再前進一步就可以了：
- 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);
為此，我們甚至可以總結出一個輔助方法：
- 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表達式定義了遞歸函數。當然，需要兩個參數的遞歸函數定義方式也比較類似。首先是SelfApplicable委托類型和對應的輔助方法：
- // 委托類型
- delegate TResult SelfApplicable(SelfApplicable self, T1 arg1, T2 arg2);
- // 輔助方法
- static Func Make(SelfApplicable self)
- {
- return (x, y) => self(self, x, y);
- } 于是使用“輾轉相除法”計算***公約數的gcd函數便是：
- var gcd = Make((f, x, y) => y == 0 ? x : f(f, y, x % y));
- Console.WriteLine(gcd(20, 36)); // 4
這也是我目前憑“個人能力”能夠走出的最遠距離了。
不動點組合子
但是裝配腦袋很早給了我們更好的解決方法：
- 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求出的是函數f的不動點，它就是我們所需要的遞歸函數：
- 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));
用腦袋的話來說，Fix方法應該被視為是內置方法。您比較Fix方法內部和之前的Make方法內部的寫法，就能夠意識到兩種做法之間的差距了。
由于我的腦袋不如裝配腦袋的腦袋裝配的那么好，即使看來一些推導過程之后還是無法做到100%的理解，我還需要閱讀更多的內容。希望在以后的某一天，我可以把這部分內容融會貫通地理解下來，并且可以詳細地解釋給大家聽。在這之前，我還是聽腦袋的話，把Fix強行記在腦袋里吧。
***，希望大家多多參與一些如“函數式鏈表快速排序”這樣的趣味編程——不過，千萬不要學腦袋這樣做：
- 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());
當然，偶爾玩玩是有益無害的。
本文來自趙劼的博客園文章《使用Lambda表達式編寫遞歸函數》
【編輯推薦】
