【专栏】康托尔、哥德尔、图灵——永恒的金色对角线（5）

一次成功的尝试

在上面几次失败的尝试之后，我们是不是就一筹莫展了呢？别忘了软件工程里面的一条黄金定律：“任何问题都可以通过增加一个间接层来解决”。不妨把它沿用到我们面临的递归问题上：没错，我们的确没办法在一个lambda函数的定义里面直接（按名字）来调用其自身。但是，可不可以间接调用呢？

我们回顾一下刚才不成功的定义：

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

现在<self>处不是缺少“这个函数自身”嘛，既然不能直接填入“这个函数自身”，我们可以增加一个参数，也就是说，把<self>参数化：

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

上面这个lambda算子总是合法定义了吧。现在，我们调用这个函数的时候，只要加传一个参数self，这个参数不是别人，正是这个函数自身。还是为了简单起见，我们用let语句来给上面这个函数起个别名：

let P = lambda self n. If_Else n==0 1 n*self(n-1)

我们这样调用，比如说我们要计算3的阶乘：

P(P, 3)

也就是说，把P自己作为P的第一个参数（注意，调用的时候P已经定义完毕了，所以我们当然可以使用它的名字了）。这样一来，P里面的self处不就等于是P本身了吗？自身调用自身，递归！

作者：刘未鹏 出版：电子工业出版社

可惜这只是个美好的设想，还差一点点。我们分析一下P(P, 3)这个调用。利用前面讲的Beta转换规则，这个函数调用展开其实就是（你可以完全把P当成一个宏来进行展开！）：

IF_Else n==0 1 n*P(n-1)

看出问题了吗？这里的P(n-1)虽然调用到了P，然而只给出了一个参数；而从P的定义来看，它是需要两个参数的（分别为self和n）！也就是说，为了让P(n-1)变成良好的调用，我们得加一个参数才行，所以我们得稍微修改一下P的定义：

let P = lambda self n. If_Else n==0 1 n*self(self, n-1)

请注意，我们在P的函数体内调用self的时候增加了一个参数。现在当我们调用P(P, 3)的时候，展开就变成了：

IF_Else 3==0 1 3*P(P, 3-1)

而P(P, 3-1)是对P合法的递归调用。这次我们真的成功了！

（待续；此文的修订版已收录《暗时间》一书，由电子工业出版社2011年8月出版。作者于2009年7月获得南京大学计算机系硕士学位，现在微软亚洲研究院创新工程中心从事软件研发工程师工作。）