如何使用Lambda表達式編寫遞歸函數

這篇文章主要介紹“如何使用Lambda表達式編寫遞歸函數”，在日常操作中，相信很多人在如何使用Lambda表達式編寫遞歸函數問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”如何使用Lambda表達式編寫遞歸函數”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

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

其實這從來不是一個很簡單的事情，雖然有些朋友認為這很簡單。

“偽”遞歸

例如，我們想要使用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表達式編寫遞歸函數”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！