数据结构学习笔记-递归

递归

基本介绍

递归是一种应用非常广泛的, 高效简洁的编程技巧, 很多数据结构和算法的编码实现都要用到递归

递归需要满足的三个条件

1. 一个问题的解可以分解为几个子问题的解
2. 原问题和分解后的子问题求解思路完全一致
3. 存在递归终止条件

写递归代码的关键

写递归代码的关键就是找如何将大问题分解成小问题的规律, 并且基于此写出递推公式, 然后推敲终止条件, 最后将递推公式和终止条件翻译成代码
只要遇到递归, 就把他抽象成一个递推公式, 不用想一层层的调用关系, 不要试图用人脑去分析递归的每一个步骤

递归常见问题

1. 堆栈溢出
   如果递归求解的数据规模很大, 调用层次很深, 一直将临时变量压入内存栈, 就会有堆栈溢出的风险
   解决办法就是限制最大的调用深度

2. 重复计算
   为了避免重复计算, 可以通过一个比如散列表来保存已经求解过的f(n), 当调用到f(n)时, 查找是否已经求解过, 如果是则直接取值, 可避免重复计算

3. 其他还有函数调用耗时高, 空间复杂度高等问题, 在编写代码时, 要控制好这些副作用