C#中的递归APS和CPS模式详解


累加器传递模式(Accumulator passing style)

尾递归优化在于使堆栈可以不用保存上一次的返回地址/状态值,从而把递归函数当成一个普通的函数调用。

递归实际上是依赖上次的值,去求下次的值。 如果我们能把上次的值保存起来,在下次调用时传入,而不直接引用函数返回的值。 从而使堆栈释放,也就达到了尾递归优化的目的。

下面我们增加了一个acc的参数,它存储上次的值,在下次调用时传入。

老赵-尾递归与Continuation

“计算n的阶乘,并将结果传入continuation方法并返回”,也就是“计算n - 1的阶乘,并将结果与n相乘,再调用continuation方法”。为了实现“并将结果与n相乘,再调用continuation方法”这个逻辑,代码又构造了一个匿名方法,再次传入Factorial方法。

总结

CPS模式是非常强大的,在很多方面都有使用,比如在编译器实现中CPS风格的解析器组合子、函数完成后回调。也可以说是把程序内部原本的控制操作,用CPS方法抽取出来暴露给程序员,例如文中的例子。


« 
» 

Copyright © 2016 phpStudy | 豫ICP备2021030365号-3