注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

中吴南顾惟一笑

成功法则就是那19个字

 
 
 

日志

 
 

尾递归  

2014-07-18 14:24:38|  分类: R&D |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

尾递归就是递归函数调用是其最后一步,然后函数就返回了,此时不必保存栈帧指针,也不用开辟新的栈空间,编译器简单的重用了当前栈空间(jmp),因此尾递归其实相当于while循环。
究其本质,其实是将递归方法中的需要的“所有状态”通过方法的参数传入下一次调用中。
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,把状态作为参数参数转移了——主程序看上去不需要维护状态了,变相解决了程序状态回溯的问题,自然也就可以轻松地变为尾递归了。

  评论这张
 
阅读(71)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017