最近看到一个系统，递归运用规则，用ocaml写的， 说到为了避免堆栈溢出，采用了CPS（Continuation_passing_style）风格。

于是深入了解一下递归与CPS的关系。

递归大家都熟悉，例如阶乘函数，递归写法如下（ocaml语法）：

let rec fact x = if (x = 0) then 1 else x* fact(x-1)

递归是语言的重要特性。 例如，在无类型的lambda演算中，可以这样写：

fact2 = λ f λn = if (n = 0 ) then 1 else n * (f f (n-1) )

当然，也可以采用大名鼎鼎的Y combinator不动点算子来计算，例如

Y = λf.(λx.f (x x)) (λx.f (x x))

fact3 = λ f λn = if (n = 0 ) then 1 else n * (f (n-1) )

则用 Y fact3 就可以求出阶乘函数了。 注意，这里的fact2和fact3 不同，虽然看上去很象，因为fact2 没有使用不动点，所以采用了一种比较原始的方式来达到递归的目的。

但上面的不动点要求语言采用lazy evaluation的方式，也就是call by name， Haskell就是这种风格，但大多数语言，例如C/JAVA等，是严格的语言，也就是说函数参数必须要在函数调用前先求出来，也就是call by value的方式。

而且这个方法只适合无类型的语言，对于Ocaml这样的带类型的严格的语言，以上方法是无法行得通的。那么， Ocaml中的不动点算子如何做呢？

let rec fix f = f (fix f)

let factabs f = function

    0 -> 1

  | x -> x * f (x-1)

let result = fix factabs 5

这个版本是无法跑通的，会出现堆栈溢出，因为fix f会无限展开。 要避免这个问题，

可以改为

let rec fix f x = f (fix f) x

let factabs f = function

    0 -> 1

  | x -> x * f (x-1)

多了一个x，即可完全行得通，有点神奇。 因为改进版的fix带两个参数，不会针对第一个参数（fix f）一直展开，（因为这个参数（fix f），返回类型也是一个函数），所以能够求出阶乘。另外一个神奇的地方是factabs需要一个参数f，但是我们没有定义，实际上也没有用到，只是利用其作为函数类型调用（x-1）.

这个只是利用了带类型的不动点算子来计算递归，实际上不需要这么复杂，用本文开头提到的fact函数就可以。 但这个函数不是尾递归的，因为最后是乘法，不是函数调用，所以不能优化，所以需要改成尾递归版本，如下：

let rec fact4 x k =

         if (x = 0 ) then k 1

         else fact4 (x-1) (fun y -> k (y*x) )

这里的k就是普通的continuation, 从本质上说，continuation是一种closure（闭包），采用闭包可以实现continuation，即所谓的Continuation_passing_style。 而c++/java目前还没有良好的闭包支持，所以如果要写类似的尾递归函数是很费劲的。

这里可以看出，闭包本质上是一个环境，并与函数计算绑定的计算环境。我们一般的函数调用是用堆栈来实现的，包括递归也是。 但是，采用闭包，我们可以使用堆来计算，而堆一般要比栈大很多，如果觉得函数递归层次太多，那么可以转化为闭包计算，也就是采用CPS风格。不但可以转化为尾递归，而且可以提供更大函数调用层次。 这也就是本文开头提到的为什么采用CPS风格的原因了。

大家可以看到，一个简单的阶乘函数，里面有很多写法，也具体反应了lazy evaluation/Continuation_passing_style/尾递归/closure等基础概念，值得仔细研究一下。