一、递归

递归可以利用前面计算的结果以求得答案。若一个对象部分地包含它自己,或用自己给自己定义,则这个对象是递归的;而且若一个过程直接或间接地调用自己,则称这个过程是递归的过程。

  1. 对于一个较复杂的问题,如果可以分解成几个相对简单的且解法相同的或类似的子问题时,只要解决这些子问题,那么原问题就迎刃而解了。

解决一个i的问题,就是解决i - 1的问题;解决i -1的问题,就是解决i - 2的问题,以此推到问题可以直接解决。

  1. 当分解之后的子问题可以直接解决时,就停止分解。这些可以直接解决的问题就是递归结束的条件。

  2. 递归定义的函数可以用递归过程来编程解决。递归过程直接反映了定义的结构

数据结构是递归的: 如后面章节所讲到的广义表

二、递推

递推是利用问题本身所具有的递推关系对问题求解的一种方法。采用递推法建立起来的算法一般具有重要的递推性质。我的理解就是可以由小规模推导出大规模,由小i - 1向大i推导。

原文:即求得问题规模为i - 1的解之后,由问题的递推性质,能从已知求得的规模为1, 2, ..., i -1的一系列的解,构造出问题规模为i的解。和递归思路相反

三、回溯法

回溯法也称为试探法,将问题的候选解按照某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就放弃它而选择下一个候选解。如果当前的解除了不满足问题规模外,其他所有要求都满足,则扩大当前候选解的规模继续试探。**放弃当前候选解,寻找下一个候选解的过程叫做回溯。**扩大当前候选解的规模,并继续试探的过程叫向前试探。

最后更新: 4/30/2019, 12:18:56 AM