转载

如何实现一个没有名字的递归函数

递归作为计算机科学中很重要的一个概念，应用范围非常广泛。比较重要的数据结构，像树、图，本身就是递归定义的。

比较常见的递归算法有 阶乘 、 斐波那契数 等，它们都是在定义函数的同时又引用本身，对于初学者来说也比较好理解，但是如果你对编程语言，特别是函数式语言，有所研究，可能就会有下面的疑问：

一个函数在还没有定义完整时，为什么能够直接调用的呢？

这篇文章主要是解答上面这个问题。阅读下面的内容，你需要有些函数式编程的经验，为了保证你能够比较愉快的阅读本文，你至少能看懂 前缀表达式 。除此之外，本文会涉及少许线性代数知识。本文所有演示代码有 Scheme 、 JS 两个版本。

问题描述

下面的讲解以 阶乘 为例子：

; Scheme (define (EXPT x n)  (if(= n0) 1  (* x (EXPT x (- n 1)))))  ; JS varEXPT =function(x, n){ if(n ==0) { return1;  } else{ returnx * EXPT(x, n-1);  } }

上面的阶乘算法比较直观，这里就不再进行解释了。我们要探究的问题是

EXPT 这个过程为什么在没有被定义完整时，就可以调用了。

问题分析

解决一个新问题，常见的做法就是类比之前解决的问题。我们要解决的这个问题和求解下面的等式很类似：

2x = x + 1

在等号两边都出现了 x ，要想解决这个问题，最简单的方式就是将等号右边的 x 移到左边即可。这样就知道 x 是什么值了。

但是我们的问题比这个要复杂些了，因为我们这里需要用 if 、 n 、 x 、 * 、 - 这五个符号来表示 EXPT ，可以这么类比是因为一个程序无非就是通过一些具有特定语意的符号（编程语言规定）构成。

再进一步思考， EXPT 需要用五个符号来表示，这和我们求解多元方程组的解不是很像嘛：

x + y = 3 x - y = 1

为了求解上面方程组，一般可以转为下面的形式：

x = 3 - y y = x - 1

即

(x, y) = T (x, y)

其中的 T 为一个转换，在线性代数其实就是个矩阵，根据矩阵 T 的一些性质，我们可以判定 (x ,y) 是否有解，以及解的个数。

对比此，我们可以把问题转化为下面的形式：

EXPT = F (EXPT)

上面的 F 为某种转换，在这里其实就是个具有一个参数的过程。如果存在这么个 F 过程，那么我们就可以通过求解 F 的不动点来求出 EXPT 了。

但这里有个问题，即便我们知道了 F 的存在，我们也无法确定其是否存在不动点，以及如果存在，不动点的个数又是多少？

计算机科学并不像数学领域有那么多可以套用的定理。

寻找转换过程 F

证明 F 是否存在是个比较难的问题，不在本文的讨论范围内，这涉及到 Denotational semantics 领域的知识，感兴趣的读者可以自己去网上查找相关资料。

这里直接给出 EXPT 对应的过程 F 的定义：

; Scheme (lambda (g)  (lambda (x n)  (if(= n0) 1  (* x (g x (- n 1))))))  ; JS varF =function(g){ returnfunction(x, n){ if(n ==0) { return1;  } else{ returnx * g(x, n-1);  }  } }

可以看到，对比递归版本的 EXPT 变动不大，就是把过程内 EXPT 的调用换成了参数 g 而已，其实我们常见的递归算法都可以这么做。

寻找转换过程 F 的不动点

找到了转换过程 F 后，下一步就是确定其不动点了，而这个不动点就是我们最终想要的 EXPT 。

EXPT = (F (F (F ...... (F EXPT) ...... )))

假设我们已经知道了 EXPT 非递归版本了，记为 g ，那么

E0= (F g) 这时(E00) 对应 (EXPT0)得值，这时用不到 g E1= (F E0) 这时(E10)、(E11)分别对应(EXPT0)、(EXPT1)的值 E2= (F E1) 这时(E20)、(E21)、(E22)分别对应(EXPT0)、(EXPT1)、(EXPT2)的值 ..... En= (F En-1) 这时....(En n)分别对应.... (EXPT n)的值

可以看到，我们在求出 (EXPT n) 时完全没有用到初始的 g ，换句话说就是 g 的取值不影响我们计算 (EXPT n) 。

那么我们完全可以这么定义 EXPT ：

EXPT = (F (F (F ...... (F 1) ...... )))

可惜，我们不能这么写，我们必须想个办法表示无穷。在函数式编程中，最简单的无穷循环是：

; Scheme ((lambda(x)(xx)) (lambda(x)(xx)))  ; JS (function(x){  return x(x); })(function(x){  return x(x); });

基于此，我们就得到函数式编程中一重要概念 Y 算子，关于 Y 算子的严格推导，可以在参考这篇文章 (译) The Y combinator (Slight Return) ，我这里直接给出：

; Scheme (define Y  (lambda (f)  ((lambda (x) (f (x x))  (lambda (x) (f (x x)))))))  (define EXPT (Y F))  ; JS varY =function(f){ return(function(x){ returnf(x(x));  })(function(x){ returnf(x(x));  }); } varEXPT = Y(F);

这样我们就得到的 EXPT 了，本文一开始给出的 EXPT 版本在解释器内部也会转换为这种形式，这也就解释了本文提出的问题，同时也给出了一个没有名字的递归函数的示例。