累加器传递模式(Accumulator passing style) 尾递归优化在于使堆栈可以不用保存上一次的返回地址/状态值,从而把递归函数当成一个普通的函数调用。 递归实际上是依赖上次的值,去求下次的值。 如果我们能把上次的值保存起来,在下次调用时传入,而不直接引用函数返回的值。 从而使堆栈释放,也就达到了尾递归优化的目的。 下面我们增加了一个acc的参数,它存储上次的值,在下次调用时传入。
使用时Accumulate递归时,我们仅需要使用最后一次的返回值即可。 调用如下:
使用Lambda表达式实现尾递归阶乘:
CPS函数 CPS全称Continuation passing style,中文一般译为后继传递模式。
上面函数将输入值乘以3,我们平常基本上都会这样写。 其实我们还可以用返回函数的C#语法,构造嵌套方式,把函数的调用变成调用链times3(3)(5)。 这种方式在数学上或函数式编程中是比较直观的,正常的,但在指令式语言c#中却不是那么直观。 CPS中的后继(Continuation)一词指的是计算的剩余部分,类似times3(3)(5)红色这部分。 例如:表达式a*(b+c)的运算过程有多个计算步骤。可以c#写成下面函数来表示:
操作步骤如下:
执行1步时,后续操作是2,3。执行2步时,后续操作是3。 使用CPS模式来改造下times3函数:
我们增加了一个表示后继操作3的函数参数,调用时传递后续操作,这就是CPS函数。 CPS变换 知道了CPS函数后,再详细看下CPS变换。
上面times3函数从直接调,到使用'后继传递操作'的过程就叫做CPS转换。 例如1:MAX函数的转换
我们把这max函数转换成CPS模式,需要下列步骤: 1:返回值修改成void 2:添加一个额外的类型参数 Action,T是原始返回类型。 3:使用后续操作表达式参数替代原来所有返回声明。
例如2:假如有3个函数Main、F、G,Main调用F、F调用G。
我们把F和G转换成CPS风格,和Max函数同样的转换步骤:
CPS尾递归 这是传统的递归阶乘:
使用同样的步骤,把递归转换成CPS尾递归:
老赵-尾递归与Continuation “计算n的阶乘,并将结果传入continuation方法并返回”,也就是“计算n - 1的阶乘,并将结果与n相乘,再调用continuation方法”。为了实现“并将结果与n相乘,再调用continuation方法”这个逻辑,代码又构造了一个匿名方法,再次传入Factorial方法。 总结 CPS模式是非常强大的,在很多方面都有使用,比如在编译器实现中CPS风格的解析器组合子、函数完成后回调。也可以说是把程序内部原本的控制操作,用CPS方法抽取出来暴露给程序员,例如文中的例子。 参考资料 http://blogs./b/wesdyer/archive/2007/12/22/continuation-passing-style.aspx DotNet 微信号:iDotNet 打造东半球最好的 .Net 微信号 -------------------------------------- |
|
来自: weijianian > 《asp.net》