Snipaste_2023-09-13_08-46-58.png
递归
何为递归
- 递归是调用自身（Call Self）的技术与艺术
- 递归将大问题分解为相似的小问题去解决
- 递归是分治算法的一种，分治算法的基本思想是把问题分解为多个较小的子问题
递归的本质：对栈（Stack）的应用
递归的本质结构是：栈结构。
递归的实现是通过函数调用栈（Call Stack）来实现的。（也可以自己去实现，利用栈结构）
递归的构成
- 基例（Base case）（或称基本情况）：递归算法必须要有可以直接求得答案的基本情况。亦称“终止条件”。
- 收敛（Convergence）：递归算法必须通过改变参数状态，不断使问题规模减小，最终达到基本情况，使递归能够结束。亦称“收敛条件”。
- 调用自身（Call Itself）：递归算法必须调用自身。调用自身是“收敛条件”的题中之义。
所以通常可以概括为：基本情况 + 收敛条件。
递归三阶段
- “递”阶段（Push阶段）：不断地对栈进行push操作，期间问题规模也在不断减小。
- 达成基本情况：问题规模最终达到基本情况，push操作停止，通过基本情况求得答案，准备开启Pop阶段。
- “归”阶段（Pop阶段）：通过已知答案，不断得出解答，从而不断地进行pop操作，直到栈为空。
第二点：达成基本情况，通常也被称作“递归终止”。
但实际上此时递归过程还没结束，“递归终止”的含义主要是在讲“递”阶段的终止。
只有达成了“递归终止”，递归才不会无限循环下去。这个角度上讲，“递归终止”有它一定的意义。
所以，我也将“达成基本情况”称作“递归终止”，而将“归”阶段的结束描述为“递归结束”。
概括为：“递”阶段 + 递归终止 + “归”阶段。
递归的实操要点：记得使用cache
递归往往都需要使用cache。
如果存在多次调用同一参数的情况，cache可以将运行速度提升好几倍，节约了运算的时间和空间。
Python的functools里面有cache和lru_cache等，需要根据问题特点，看情况作出选择。
递归的一个重要的Error：最大递归深度超过限制。RecursionError：maximum recursion depth exceeded。
RecursionError: maximum recursion depth exceeded while calling a Python object
获取当前的最大递归深度：通常是1000。
import sys
print(sys.getrecursionlimit())
这可以通过sys.setrecursionlimit() 来进行设置，但最高限度取决于系统即运行平台。
官网是这么说的：
不同平台所允许的最高限值不同。当用户有需要深度递归的程序且平台支持更高的限值，可能就需要调高限值。进行该操作需要谨慎，因为过高的限值可能会导致崩溃。
所以这个一般情况下不要更改。使用默认的就够了。
递归经典案例
阶乘是永恒的经典
def fact(n):
# Base Case
if n == 0:
return 1
# Convergence
else:
return n * fact(n - 1)
Fibonacci数列亦是
from functools import cache
@cache
def fib(n):
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
