Haskell
值得注意的一些重要概念 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保存.