使用Lambda表達式編寫遞歸一：前言及基礎
前言
這是一個比較古老的話題，三年半之前，老趙就此寫過一篇很文章《使用Lambda表達式編寫遞歸函數》。其中提出了偽遞歸的概念，提出了自己的解決方式，也引出了裝配腦袋 使用不動點組合子 的解決辦法。此后好長一段時間，偽遞歸和不動點組合子成了兩個園子里的兩大熱門話題。
當年我也寫了篇文章《反駁 老趙 之 “偽”遞歸》參與了爭論，不過對老趙提出的解決方式及裝配腦袋的不動點組合子思路，一直沒弄清楚。中間一段時間，工作忙，忘卻了。
最近比較輕閑，靜下心來學習了下相關的的一些理論，并深入思考，略有所悟，在此和大家分享下。
本文及后續章節會用到相當復雜的泛型及 lambda 表達式，請做好相關技術和心理準備。
使用 Lambda 表達式構建遞歸函數
很多朋友認為這很容易，隨手便可用 lambda 表達式寫出一個階乘遞歸：
- Func<int, int> fact = x => x <= 1 ? 1 : x * fact(x - 1);
不過，很抱歉，這行代碼是無法通過編譯的，VS 提示：使用了未賦值的變量 fact。
有種簡單的解決辦法，把上面這行代碼拆成兩行：
- Func<int, int> fact = null;
- fact = x => x <= 1 ? 1 : x * fact(x - 1);
不過這種寫法也有問題，老趙說得比較清楚，我就不在贅述了，請查看《使用Lambda表達式編寫遞歸函數》一文中偽遞歸部分。
那么如何解決 lambda 表達式構建遞歸函數的問題呢？根據函數式編程理論，我們可以使用不定點組合子。
在學習不定點組合子之前，需要先了解更基礎 λ 演算。
λ 演算
λ 演算的基礎請大家參考維基百科：
http://zh.wikipedia.org/wiki/Lambda_演算
http://en.wikipedia.org/wiki/Lambda_calculus
非形式化的描述
請確保你已經理解了文中幾個表達式的等價關系：
- (λf. f 3)(λx. x + 2) == (λx. x + 2) 3 == 3 + 2
- (λx. λy. x - y) 7 2 == (λy.7 - y) 2 == 7 - 2
還清楚知道函數應用（application）的概念及其左結合性：
- f x y == (f x) y
還有它的各種等價變換
- f x y == (f x) y = (f(x))y = (f(x))(y) = f(x)(y)
歸約
并會運用三個常用的規約（Reduction）
1.α-變換（α-conversion）
2.β-歸約（β-reduction）
3.η-變換（η-conversion）
不動點組合子
請參考：
http://zh.wikipedia.org/wiki/不動點組合子
http://en.wikipedia.org/wiki/Fixed-point_combinator
定義
不動點組合子（Fixed-point combinator，或不動點算子，使用 FIX 表示）是計算其他函數的一個不動點的高階函數。
不動點算子具有以下特性，對于任何函數 f 都有：
- FIX ff = f (FIX f)
定義匿名的遞歸函數
不動點組合子允許定義匿名的遞歸函數，具體來說是將一個非遞歸的單步函數（只執行遞歸中的一步，a single step of this recursion，使用 g 表示）轉換為遞歸函數。
如下是階乘的單步函數定義：
- g = λf. λn. (ISZERO n) 1 (MULT n (f (PRED n)))
FIX g 可獲取到匿名的遞歸函數：
- FIX g = λn. (ISZERO n) 1 (MULT n ((FIX g) (PRED n)))
向 FIX g 的參數 n 傳入值 5，可最終得出：
- FIX g 55 = 5 * (4 * (3 * (2 * (1 * 1)))) = 120
常用的不定點組合子
不動點組合子中最有名的（也可能是最簡單的）是 Y 組合子：
- Y = λf. (λx. f (x x)) (λx. f (x x))
另一個常見不動點組合子是圖靈不動點組合子（阿蘭·圖靈發現的）:
- Θ = (λx. λy. (y (x x y))) (λx.λy.(y (x x y)))
傳值調用（call-by-value）
在 λ 演算中，每個表達式（lambda term）都代表一個只有單獨參數的函數，這個函數的參數本身也是一個只有單一參數的函數，同時，函數的值是又一個只有單一參數的函數。
根據此描述，可知 λ 演算中函數只有一個參數，這個參數是一個函數，而不是一個值。而對于我們常見的遞歸（階乘、斐波那契數列求值），參數都是值（自然數）。兩者是不匹配的。
為了適當傳值調用，需要將不動點組合子 η-展開：
簡單而言 η-變換 是說 λx. f x 和 f 可以互相轉換。從 f 這種簡單形式 η-變換 為 λx. f x 復雜形式，稱為 η-展開。
對于 Y 組合子，通常是將其中的 (x x) η-展開為 λy. x x y，由此得出傳值調用版本的 Y組合子（也稱為 Z 組合子）：
- Y = λf. (λx. f (λy. x x y)) (λx. f (λy. x x y))
如果不展開呢？會怎樣？
如果使用不展開的不動點算子，也能寫出可編譯通過的代碼，但最終執行會陷入死循環，直至堆棧溢出。
小結
后續章節將使用以下符號和名稱，不再另行說明：
1.FIX：不動點組合子
2.g：單步函數
3.n：表示遞歸函數的參數（在階乘、斐波那契數列求值中是一個自然數）
對于 FIX、g、n：
1.FIX g： 將會生成對應的遞歸函數
2.FIX g n： 將進行遞歸運算
λ 演算表達式與 c# lambda 表達式的對應關系
λx. x + 2
λx. x + 2 在 c#中的 lambda 表達式可表式為：x => x+ 2；
假定 x 的 int 類型，可寫作：
- Func<int, int> f = x => x + 2;
相應 (λx. x + 2) 1 可寫為：
- var result = f(1); // 結果為 3
λx. λy. x + y
復雜點，λx. λy. x + y 用 c# 的 lambda 表達式表示為：x => y => x + y；
x, y 類型為均整數時，可寫作：
- Func<int, Func<int, int>> f = x => y => x + y;
相應 (λx. λy. x + y) 1 2 便是：
- var result = f(1)(2); // 結果為 3
λx. λy. λz. x + y + z
再復雜些，λx. λy. λz. x + y + z 表示為：x => y=> z => x + y + z，三個參數都為 int 時 c# 代碼：
- Func<int, Func<int, Func<int, int>>> f = x => y => z => x + y + z;
可如下調用：
- // (λx. λy. λz. x + y + z) 1 2 3
- var result1 = f(1)(2)(3); //結果為 6
- // (λx. λy. λz. x + y + z) 1 → λy. λz. 1 + y + z
- Func<int, Func<int, int>> g = f(1);
- // (λy. λz. 1 + y + z) 2 → λz. 1 + 2 + z → λz. 3 + z
- Func<int, int> h = g(2);
- // (λz. 3 + z) 3 → 3 + 3 → 6
- var result2 = h(3); // 結果為 6
每 5 行，向 f 傳入一個常量 1，返回一個新的方法 g；再經過第 7 行，向 g 傳入常量 2，再次返回一個新方法 h。
方法 h 只能接受一個參數，***得出 h(3) = 6。
為什么不是 (x, y, z) => x + y + z？
也許你會有疑問，不就是 x、y、z 三個整數加起來嘛，為什么搞這么復雜，像下面這樣不是更簡單嗎？
- Func<int, int, int, int> f = (x, y, z) => x + y + z;
- var result = f(1, 2, 3);
確實簡單，不過：
在 λ 演算中，每個表達式（lambda term）都代表一個只有單獨參數的函數，這個函數的參數本身也是一個只有單一參數的函數，同時，函數的值是又一個只有單一參數的函數。
注意都是只有一個參數，對應到 c# 的 lambda 表達式，也應是一個參數，所以是：x => y=> z => x + y + z。
總結
| λ 演算表達式 | c# lambda 表達式 |
| λx. x + 2 | x => x+ 2 |
| λx. λy. x + y | x => y => x + y |
| λx. λy. λz. x + y + z | x => y=> z => x + y + z |
好像有些規律：對于一個 Lambda terms，去掉“λ”并把“.”替換為”=>”便可變成對應 lambda 表達式。（注意，這個規律不嚴謹！）
練習一下，看看下面這個如何轉為 lambda 表達式：
- λx. λn. (g (x x) n)
先對它進行一步演算得出：
- λx. λn. (g (x(x)) (n))
運用上的的規律，可以寫出 lambda 表達式：x => n => g((x(x))(n)
對于復雜點的如：λx. f ( λv. (x x) v)，這條規律就不適用了。文后續部分會通過演算繞開這種復雜的轉換，不對此進行討論。
理解本文中的泛型和 lambda 表達式
對于上一部分使用的泛型和 lambda 表達式，尤其是下面這行代碼，你需要花點時間去理理思路（因為后續章節中泛型要遠比此復雜）：
- Func<int, Func<int, Func<int, int>>> f = x => y => z => x + y + z;
如果對你對泛型和 lambda 認識不是非常深刻的話，難度有點大，不妨先從下面這個簡單點的開始：
- Func<int, Func<int, int>> f = x => y => x + y;
換種寫法，或許有助于理解：
- Func<int, Func<int, int>> f = x => {
- Func<int, int> g = y => { return x + y ;};
- return g;
- };
本文簡單闡述了 lambda 構建遞歸函數的問題，粗略提及 λ 演算及不動點組合子的知識，并總結了下 λ 演算表達式與 c# lambda 表達式的對應關系。
原文鏈接：http://www.cnblogs.com/ldp615/archive/2013/04/09/recursive-lambda-expressions-1.html
