值得注意的一些重要概念
cps
cps全称叫continuation passing style，简要来讲就是告诉函数下一步做什么的递归方式，由于普通递归有栈溢出的问题，而cps都是尾递归(tail recursion)，尾递归则是没有栈溢出问题的，所以haskell推荐都用cps的方式去编写代码。
当然，相对于普通递归方式，cps也有着非常不便于理解的问题。
def fact(n): if (n==0): return 1 else: return n* fact(n-1) print fact(400) 这是一段递归求阶乘的python代码。用cps改写就是
def fact_cps(n,ret): if (n==0): ret(1) else: fact_cps(n-1, lambda x:ret(n*x)) def ret2(x): print x fact_cps(400,ret2) 这里要注意的是，我们在传参数的时候多了一个ret，而这个ret其实是一个函数，函数的作用就是传入一个值并打印他。在实际运行过程中，其实是这样子的
以fact_cps(3,ret2)求3的阶乘为例，第一步我们是执行fact_cps(3,ret2)，到第五行的地方，我们执行的是fact_cps(2, lambda x:ret2(3*x))，这里的ret即最外层的ret2
fact_cps中的lambda x:ret (3x)其实是一个函数的简单写法，也就是说这是一个输入x的函数，然后运算ret(3x)
第二步调用以后，fact_cps的输入值是2以及一个叫做lambda x:ret(3x)的函数，也就是说ret函数变成了ret(x): print (3x) 然后到第五行调用fact_cps(1,lambda x:ret(2x))即fact_cps(1,lambda x:ret2(32*x))
第三布调用的就是fact_cps(0,lambda x:ret2(321x))，然后到第三行结束，所以总的一个计算其实就是lambda x:ret2(321x)然后将最后一次调用的1带入，得到6。
这中间我们可以看到，和普通递归传递的是参数不同，cps调用每一步都产生一个新的函数，传递给下一步调用，这个传递的函数告诉了被递归函数下一步做的是什么。
尾递归
尾递归就是从最后开始计算, 每递归一次就算出相应的结果, 也就是说, 函数调用出现在调用者函数的尾部, 因为是尾部, 所以根本没有必要去保存任何局部变量. 直接让被调用的函数返回时越过调用者, 返回到调用者的调用者去。尾递归就是把当前的运算结果（或路径）放在参数里传给下层函数，
线性递归:
long Recursive(long n) {
return(n == 1) ? 1 : n * Recursive(n - 1);
}
尾递归:
long TailRecursive(long n, long a) {
return(n == 1) ? a : TailRecursive(n - 1, a * n);
}
long TailRecursive(long n) {//封装用的
return(n == 0) ? 1 : TailRecursive(n, 1);
}
当n = 5时
对于线性递归, 他的递归过程如下:
Recursive(5)
{5 * Recursive(4)}
{5 * {4 * Recursive(3)}}
{5 * {4 * {3 * Recursive(2)}}}
{5 * {4 * {3 * {2 * Recursive(1)}}}}
{5 * {4 * {3 * {2 * 1}}}}
{5 * {4 * {3 * 2}}}
{5 * {4 * 6}}
{5 * 24}
120
对于尾递归, 他的递归过程如下:
TailRecursive(5)
TailRecursive(5, 1)
TailRecursive(4, 5)
TailRecursive(3, 20)
TailRecursive(2, 60)
TailRecursive(1, 120)
120
//
#include <stdlib.h>
#include <stdio.h>
long TailRecursive(long n, long a) {
return(n == 1) ? a : TailRecursive(n - 1, a * n);
}
long TailRecursive(long n) {
return(n == 0) ? 1 : TailRecursive(n, 1);
}
int main()
{
printf("%ld", TailRecursive(5));
return 0;
}
####tail recursion in haskell
sum' :: (num a) => [a] -> a -> a
sum' (x:xs) temp = sum' xs x+ temp
sum' [] temp = temp
我们这样调用它: sum' [1,2,3] 0。
它的执行顺序是这样的:
sum' [1,2,3] 0 ->
sum' [2,3] 1 ->
sum' [3] 3 ->
sum' [] 6 ->
6
很容易看出, 普通的线性递归比尾递归更加消耗资源, 在实现上说, 每次重复的过程 调用都使得调用链条不断加长. 系统不得不使用栈进行数据保存和恢复.而尾递归就 不存在这样的问题, 因为他的状态完全由n和a保存.