数据结构第二季 Day13 递归 、斐波那契数列

一、初识递归

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