[AlgoGo]递归
2020-09-22 本文已影响0人
周瑞不是同端
什么是递归？
递归就是自己调用自己。
什么样的问题可以用递归来解决？
- 一个问题的解可以分为几个规模更小的子问题的解。
- 分解后的子问题除了规模更小，解决思路完全相同。
- 存在递归终止条件。
同时满足上述3个条件的问题可以用递归解决。
如何写出递归代码？
递推公式 + 递归终止条件
递归需要注意哪些问题？
堆栈溢出：函数反复压栈导致堆栈溢出
解决方案：限制最大递归层数，超过最大层数抛出异常。
重复计算：子问题求解过程重复计算
解决方案：记录求解结果，判断子问题是否已求解。
所有递归代码均可以转换为非递归的实现（使用循环手动模拟压栈）
