首选是说下尾递归.如果一个函数呈现下列情况,且中间没有再次递归使用自己,可以认为是一个尾递归.

R function(a,b)

{

　　......

　　return function(c,d);

}

尾递归可以很轻松的改为一个循环的,如果编译器(解释器)支持的话,可以直接优化的.一般的FP都支持尾递归的.

如果像树,Fibonacc这种结构来使用递归的,好像很难转化为尾递归的,这时候使用到的另一种方法是Continuation ,Continuation 可以是看做是一个尾递归的,不过得把 b,d 看做函数它们有着相同的函数签名.

看个例子把

let rec fib n =     match n with    | 0|1 -> n        |_ -> fib (n-1)+fib (n-2)

简单的fibonacc程序,如果这个改成continuation结构的话如下:

let fibonacci_cps n =   let rec fibonacci_cont a cont =     if a <= 2 then cont 1     else       fibonacci_cont (a - 2) (fun x ->         fibonacci_cont (a - 1) (fun y ->            cont(x + y)))              fibonacci_cont n (fun x -> x)

fibonacci_cont 函数中展开了结果函数调用.原来的程序是将函数放在了栈上,而这个函数相当于在堆上生成了很多的函数对象.其实程序的复杂度没有变化的.

 

再看下C++中的continuation,本来想使用c++0x来重写上面的例子的,但是发现不行主要是c++lambda支持"对lambda外部局部变量引用无效",二即使写出来最终的结果也是放在堆上的.

当然这个时候有个解决方案,使用传说中的tbb.

tbb中task是带continuation应用的.在讨论tbb前,我们先看下 return fib(n-1)+fib(n-2)的含义.在栈上.调用函数将n-1 和 n-2分别给了函数 fib fib,在这两个函数结束之前是不能够运行本函数的,好了这个时候我们就发现了我们需要在堆上模拟这种情况.一个函数对象,它能够调用2个函数,并且在这2个函数调用之前它自己不能运行.

好了直接上代码了,代码中有解释的

struct FibContinuation: public task {   long* const sum;   long x, y;   FibContinuation( long* sum_ ) : sum(sum_) {}   task* execute() {   *sum = x+y;        //fib(n-1)+fib(n-2)   return NULL;   }};struct FibTask: public task {   const long n;   long* const sum;   FibTask( long n_, long* sum_ ) : n(n_), sum(sum_) {}   task* execute() {      if( n

当然tbb中的运行顺序是并行的 fib(n-1) fib(n-2), 而在c++中 fib(n-1)+fib(n-2)可能是先完成fib(n-1)或者是fib(n-2)的总之是先完成一部分的.

continuation可以认为是先生成一颗巨大的函数调用树,不过这颗树是在堆中而已.

最后给下普通调用与continuation的图示.

这个是普通的调用,调用函数必须等到下面的两个儿子搞定,而continuation调用如下,

调用函数生成continuation然后将两个儿子的返回指向了continuation,运行两个儿子,然后parent自行结束,所以不会得在栈保存东西.

当然tbb还有更猛的优化叫recycle_as_continuation,毕竟生成一个对象是耗时间的,可以回收利用.

当然这个是我的理解.如有错误还请高手指正.

参考.

1. 上面的代码的完整代码

2.赵姐夫的blog 

3.<C#与F#编程实践> 其实想写这篇文章的主要原因是看这个上面讲到的,虽然这本书没有让我崩掉几个牙齿,但是让我没睡好觉.