递归的理解
目录
什么是递归
方法或函数调用自身的方式称之为递归,调用成为递,返回称为归。
优缺点
-
优点:代码简洁表达能力强。
-
缺点:空间复杂度高,栈溢出,存在重复计算。
递归使用场景
满足以下三个条件,就可以使用递归:
-
问题的解可以分解为几个子问题的解,何为子问题?就是数据规模更小的问题。
-
问题与子问题,除了数据规模不同,求解思路完全一样。
-
存在递归终止条件。
如何实现
1. 编写
关键是找到如何将大问题分解为小问题的规律,写出递归公式,推敲终止条件,最后翻译成实际的代码。
2. 理解
避免思维误区:不要试图去想清楚整个递和归的过程。 那怎么想?如果问题 A 可以分解为 B、C、D 三个子问题,可以假设 B、C、D 已经解决。只需要思考问题 A 和 子问题之间的关系即可。