那谁的技术博客

感兴趣领域:高性能服务器编程,存储,算法,Linux内核
随笔 - 210, 文章 - 0, 评论 - 1183, 引用 - 0
数据加载中……

递归和递推的非严格概念解释

递归:解决一个问题的时候可以分解为更小的问题,而且分解之后的问题的解决方法和原来的一致,这时可以把问题一直这么分解下去,直到问题分解到足够小的时候进行解决,然后再回溯回去解决原来的问题.

递推:类似于数学归纳法中的归纳步骤,假设某个问题在某一步时某个条件成立,下一步可以根据这一步所得的关系进行推导,这就是递推.

本质上,递归和递推都是同一种解决问题的思路,就是把问题分解中较小的问题,但是递归是由大到小的推导直到问题规模足够小可以不必继续推导就可以解决了,而递推是由小到大的推导,采用递推解决问题的有KMP算法之中寻找next数组元素值的算法.

递归,一般的算法书上都有明确的定义,而递推我印象之中还没有非常严格的说明.在这里根据我的理解作一个解释,也许不完全对,请大家指正.

posted on 2006-07-09 21:43 那谁 阅读(1314) 评论(1)  编辑 收藏 引用 所属分类: 算法与数据结构

评论

# re: 递归和递推的非严格概念解释  回复  更多评论   

有递推这种算法形式吗?还是说,只是为了与递归对应,不是递归就是递推?
文中的解释,觉得是从算法上来说明。其实,递归,应该是一种计算机的算法表达形式,它指的应该是有限制的直接或间接重复调用自身的一种子程序。
2006-07-10 09:14 | 沐枫

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理