究其本质,其实是将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中。
solve_problem(args)
{
if(satisfy_exit_condition)
{
exit;
}
else
{
split problem;
select sub-problem i;
return solve_problem(args_i);
}
}
solve_problem(args)
{
while(1)
{
if(satisfy_exit_condition)
{
exit;
}
split problem;
select sub-problem i;
args = args_i;
}
}
而循环(迭代)和一般递归的相互转换涉及到图灵完备性问题。即要用简单的循环来代替一般递归的话,有些情况必须要维护一个额外的递归数据结构(处理上下文无关文法的下推自动机就是比处理正则文法的有限状态自动机多了一个栈)。而递归自然地将这个数据结构隐藏在了调用栈之中,所以是一种更高级的抽象手段,代码可读性也更佳。
在函数式编程中,要实现“循环”的唯一方法便是“递归”,因此尾递归和Continuation Passing Style(CPS)对于函数式编程的意义非常重大。
Continuation可以把任意递归包装成尾递归形式。在不改变算法本身的情况下,Continuation做了一层掩饰,就是利用这个Continuation Callback,把状态作为参数参数转移了——主程序看上去不需要维护状态了,变相解决了程序状态回溯的问题,自然也就可以轻松地变为尾递归了。
评论