一、初识递归
1、递归的定义？递归是算法思想或者算法策略吗？
-
递归的定义：函数（方法）直接或者间接调用自身。 - 严格来讲递归不是算法思想或者算法策略，只是一种常用的编程技巧。
image.png
2、生活中一些有趣的递归现象，好好品，加深理解。
image.png
3、自己手动绘制下面函数栈空间建立和释放的过程（多感悟下栈空间）？
image.png
image.png
4、递归调用如果没有边界条件，会出现什么问题？
- 如果递归调用没有终止条件，将会一直消耗栈空间。最终导致栈内存溢出（Stack Overflow）
5、递归一定是最优解吗？如果不一定是，那么递归有什么好处？
- 递归求出来的很可能不是最优解，也可能是最优解。
- 递归不是为了求得最优解，是为了简化解决问题的思路，代码会更加简洁
image.png
6、递归的基本思想（重要的思想）？
拆解问题- 把规模大的问题变成规模较小的
同类问题 - 规模较小的问题又不断变成规模更小的同类问题
- 规模小到一定程度就可以直接得出它的解
求解- 由最小规模问题的解得出较大规模问题的解
- 由较大规模问题的解不断得出规模更大问题的解
- 最后得出原来问题的解
image.png
7、为什么链表、二叉树的很多相关问题，都可以尝试使用递归？
- 因为链表、二叉树本身就是递归的结构（链表中包含链表、二叉树中包含二叉树）
8、递归的使用套路（本章最重要）？
- ①明确函数功能
- 先不要去思考代码里面怎么写，首先搞清楚这个函数是干嘛用的，能完成什么功能？
- ②明确原来问题与子问题
- 寻找 f(n) 与 f(n-1)的关系
- ③明确递归基（边界条件）
- 递归的过程中，子问题的规模在不断减小，当小到一定程度时可以直接得出它的解
- 寻找递归基，相当于是思考：问题规模小到什么程度可以直接得出解？
二、经典递归问题：斐波那契数列的故事
1、什么是斐波那契数列？
image.png
2、为什么时间复杂度是 O(2^n)？
- 如下图所示，每次调用，数据函数规模都是原来的两倍
- 每个函数里面都需要执行一个加法
- 所以综合来说，时间复杂度就是 O(2^n)，这个时间复杂度是非常恐怖的😱
image.png
3、递归函数的空间复杂度怎么计算？为什么斐波那契数列的空间复杂度是 O(n)?
- 基础认知：递归调用的空间复杂度 = 每一次调用函数的辅助空间 * 递归最大深度
- 把握最关键的信息，在 F(n-1) 计算完毕之前，F(n-2)是不会被执行也不会分配栈空间的。
-
所以上述斐波那契数列的空间复杂度就是 O(n-1)，去除常数项，就是 O(n)
image.png
4、使用数组来存放已经计算过的 F(n)，防止重复计算。优化第一版如下
image.png
5、去除递归调用。优化第二版如下
image.png
6、观察发现优化第二版其实仅仅使用到数组中的 2 个元素，所以可以使用滚动数组来优化。优化版本三如下
image.png
- 乘、除、模运算效率比较低，建议使用其他方式取代
- 那么 n % 2 ，可以用其他方式取代吗？
- 注意观察，其实 n % 2 本质上是看 n 的二进制数据最低位上是 0 还是 1
- 所以
n % 2等价于n & 1
image.png
7、观察发现，就用到数组两个元素，其实直接用两个变量即可啊。优化版本四如下
image.png
8、对于斐波那契数列，后面又研究出了特征方程，优化版本五如下（了解即可）？
image.png
