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)

递归：yyds！