学习笔记|数据结构与算法之递归

递归

递归需要满足的三个条件

1. 一个问题的解可以分解为几个子问题的解

2. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样

3. 存在递归终止条件

总结：

写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码

注意：

递归要警惕堆栈溢出，当递归次数过大时，超出JVM内部堆栈。便会抛出Exception in thread "main" java.lang.StackOverflowError

避免堆栈溢出就需要限制最大递归深度

警惕重复计算，递归一般会出现二叉树形式的计算链，每次都往Map中存储当前计算结果，从而避免重复计算。