递归算法设计

  2017-10-19 


一、递归算法设计

设计一个递归算法,先要搞清楚最基本的模型

先考虑最小模型(最基本模型)应该如何操作

写出基本模型和递推式之后,再确定参数传递

其中注意抓住(单或多)入口与(单或多)出口

进入入口之后就不要管其中间过程,将他们视为整体,转而去出口语句处,思考对最小单元执行什么内容,判断是否出栈。

(即只管整体(入栈)与最小单元(出栈口判断与操作))

(这时候结合二叉树递归遍历就很好理解。

对于栈底,先遍历左子树,然后第二条语句执行时,第一条语句遍历左子树已经执行结束,也就是说对于栈底层来说,左子树已经完全遍历结束

这对于每一个中间节点都是成立的,我们只需要考虑当层,不用管中间过程,这个中间过程就是递归,我们在设计最小单元、入口出口的时候就已经设计好了)

二、递归大体等效为两种

一种等效于正向循环(直到不满足前一直执行),另一种回溯(直到满足条件再反向执行)

这取决于执行体相对于递归语句的位置

递归思想在树与图中应用广泛,可以说是重要爆了

设计算法要充分发掘隐含实际情况的隐含特性

TBC.


且听风吟