算法专题:递归 vs 迭代(栈)

递归 vs 迭代(栈)

递归

尾递归可以转化为迭代;
存在重叠子问题最优子结构的递归问题,最好是转化为动态规划(DP

递归树

解决递归问题最好是画出递归树,方便分析算法复杂度,找出算法低效的原因。
比如说Fibonacci数列的递归树中可以看到,使用递归求解时单个项需要重复计算多次,算法十分低效:

时间复杂度

递归算法的时间复杂度 = 子问题个数 x 解决一个子问题需要的时间

  1. 子问题个数:递归次数(即递归树中子节点个数,比如Fibonacci数列递归树是二叉树,所以节点数量为2^n
  2. 解决一个子问题需要的时间:比如Fibonacci数列单次递归只需要进行一次加法计算,时间复杂度为O(1),所以总时间复杂度为O(2^n)

递归函数模板

  1. 刚进递归函数,就要指明跳出递归的条件
  2. 处理当前层
  3. 递归到下一层
  4. 如果有必要的话,还原当前层状态
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func recursion(level, param1, param2, ...) {
//1. recursion terminator
if level > MAX_LEVEL {
return data...
}

//2. process logic in current level
process_data(level, data...)

//3. drill down
recursion(level + 1, p1, ...)

//4. reverse the current level status if needed
reverse_state(level)
}
-------------本文结束感谢您的阅读-------------

本文标题:算法专题:递归 vs 迭代(栈)

文章作者:DragonBaby308

发布时间:2019年08月09日 - 07:33

最后更新:2020年02月01日 - 14:50

原始链接:http://www.dragonbaby308.com/Algorithm-Recursion-Iteration-Stack/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%