V2采用标准累积变量完成尾递归:
loop ([0;1;2;3;4;5;6;7;8], []) ->
loop ([3;4;5;6;7;8], [(0,1,2)]) ->
loop ([6;7;8], [(3,4,5), (0,1,2)]) ->
loop ([], [(6,7,8), (3,4,5), (0,1,2)]) ->
[(6,7,8), (3,4,5), (0,1,2)]
V3 uses 延续 http://en.wikipedia.org/wiki/Continuation_passing_style,或者用简单的英语来说,累积功能:
loop ([0;1;2;3;4;5;6;7;8], x->x) ->
loop ([3;4;5;6;7;8], x->(0;1;2)::x) ->
loop ([6;7;8], x->(3;4;5)::x) ->
loop ([], x->(6,7,8)::x) ->
[(6,7,8)] // x->(6,7,8)::x applies to []
->
[(3,4,5);(6,7,8)] // x->(3,4,5)::x applies to [(6,7,8)]
->
[(0,1,2);(3,4,5);(6,7,8)] // x->(0,1,2)::x applies to [(3,4,5);(6,7,8)]
您可以看到累加变量和累加函数之间的区别:
使用累积变量在最后一次调用时停止,因为累积变量存储答案。然而,累加函数仍然做了一些事情回溯最后一次通话后继续工作。应该注意的是,使用累积函数确实是尾递归,因为递归调用loop t (fun ls -> accfun ((a,b,c)::ls))
实际上是last这个函数的声明。
顺便说一句,您提供的代码是展示尾递归函数概念的一个很好的例子。理解这些示例代码的一种方法是处理小案件正如我在上面两个插图中所做的那样。经过一些小案例的练习,你会对这个概念有更深入的理解。