【專欄】康托爾、哥德爾、圖靈——永恒的金色對角線（4）

遞歸的迷思

敏銳的你可能會發現，就以上這兩條公理，我們的lambda語言中無法表示遞歸函數，為什么呢？假設我們要計算經典的階乘，遞歸描述肯定像這樣：

f(n):

if n == 0 return 1

return n*f(n-1)

當然，上面這個程序是假定n為正整數。這個程序顯示了一個特點，f在定義的過程中用到了它自身。那么如何在lambda算子系統中表達這一函數呢？理所當然的想法如下：

lambda n. If_Else n==0 1 n*<self>(n-1)

當然，上面的程序假定了If_Else是一個已經定義好的三元操作符（你可以想象C的“?:”操作符，后面跟的三個參數分別是判斷條件、成功后求值的表達式、失敗后求值的表達式。那么很顯然，這個定義里面有一個地方沒法解決，那就是<self>那個地方我們應該填入什么呢？很顯然，熟悉C這類命令式語言的人都知道應該填入這個函數本身的名字，然而lambda算子系統里面的lambda表達式（或稱函數）是沒有名字的。

作者：劉未鵬 出版：電子工業出版社

怎么辦？難道就沒有辦法實現遞歸了？或者說，丘齊做出的這個lambda算子系統里面根本沒法實現遞歸從而在計算能力上面有重大的缺陷？顯然不是。馬上你就會看到Y combinator是如何把一個看上去非遞歸的lambda表達式像變魔術那樣變成一個遞歸版本的。在成功之前我們再失敗一次，注意下面的嘗試：

let F = lambda n. IF_Else n==0 1 n*F(n-1)

看上去不錯，是嗎？可惜還是不行。因為let F只是起到一個語法糖[1]的作用，在它所代表的lambda表達式還沒有完全定義出來之前你是不可以使用F這個名字的。更何況實際上丘齊當初的lambda算子系統里面也并沒有這個語法元素，這只是剛才為了簡化代碼而引入的語法糖。當然，了解這個let語句還是有意義的，后面還會用到。

【注釋】

[1]語法糖是編程語言中的一種說法，其作用在于使對象便于閱讀和表達。

（待續；此文的修訂版已收錄《暗時間》一書，由電子工業出版社2011年8月出版。作者于2009年7月獲得南京大學計算機系碩士學位，現在微軟亞洲研究院創新工程中心從事軟件研發工程師工作。）