5. 递归函数
递归函数就是一个函数在它的函数体内调用它自身。执行递归函数将反复调用其自身，每调用一次就进入新的一层。
递归函数通常包含两个关键部分：
- 递归终止条件：这是一个判断语句，用于确定何时停止递归调用。如果没有终止条件，函数将无限递归，最终导致栈溢出错误（因为每次递归调用都会在调用栈中增加一层，栈空间是有限的）。例如，在计算阶乘的递归函数中，
n == 0或n == 1就是递归终止条件，因为0!和1!都等于 1。 - 递归调用：函数在满足终止条件之前，会调用自身来处理问题的一部分。每次递归调用时，问题的规模会逐渐减小，直到满足终止条件。例如，在计算阶乘
n!时，n! = n * (n - 1)!，这里(n - 1)!就是通过递归调用计算得到的，随着递归的进行，n的值不断减小，直到满足终止条件。
💡 设计递归函数三要素
1. 明确你这个函数想要干什么
2. 寻找递归结束条件
3. 找出函数的等价关系式
⚠️ 递归与循环的关系
但凡循环能够解决的问题，递归都可以；但是递归解决的问题，循环不一定！
因为函数是装载在内存的栈内存中的，递归函数层数过多，非常容易导致栈内存溢出的问题，我们就得需要控制一下递归的深度/层数。所以，递归一般用来解决层数较少的问题。
例1：递归输出 1 到 10
python
# 写法1
def num(n):
if n <= 10:
print(n) # 输出在递归前
num(n + 1)
num(1)
# 写法2
def num(n):
if n >= 1:
num(n - 1)
print(n) # 输出在递归后
num(10)▶ 运行结果：
输出
1
2
3
4
5
6
7
8
9
10
1
2
3
4
5
6
7
8
9
10例2：计算阶乘 n!
n! = n * (n - 1) * (n - 2) * ... * 1，并且规定 0! = 1。
分析：例如 5! = 5 * 4 * 3 * 2 * 1 = 5 * (4 * 3 * 2 * 1) = 5 * 4 * (3 * 2 * 1) = 5 * 4 * 3 * (2 * 1)
python
def ni(n):
if n == 0 or n == 1:
return 1
else:
return n * ni(n - 1)
# 计算5的阶乘
print(ni(5))▶ 运行结果：
输出
120例3：递归函数的返回值（递归前与递归后）
python
def p(n):
if n == 0:
return
print('递归前->', n)
p(n - 1)
print('递归后->', n)
p(5)▶ 运行结果：
输出
递归前-> 5
递归前-> 4
递归前-> 3
递归前-> 2
递归前-> 1
递归后-> 1
递归后-> 2
递归后-> 3
递归后-> 4
递归后-> 5当执行 p(5) 时，程序流程如下：
- 初始调用
p(5)，n 为 5，不满足终止条件。打印递归前-> 5。 - 调用
p(4)，n 为 4。打印递归前-> 4。 - 调用
p(3)，n 为 3。打印递归前-> 3。 - 调用
p(2)，n 为 2。打印递归前-> 2。 - 调用
p(1)，n 为 1。打印递归前-> 1。 - 调用
p(0)，n 为 0，满足终止条件，p(0)函数返回。 - 返回到
p(1)，打印递归后-> 1。 - 返回到
p(2)，打印递归后-> 2。 - 返回到
p(3)，打印递归后-> 3。 - 返回到
p(4)，打印递归后-> 4。 - 返回到
p(5)，打印递归后-> 5。
python
# 输出结果：
# 递归前-> 5
# 递归前-> 4
# 递归前-> 3
# 递归前-> 2
# 递归前-> 1
# 递归后-> 1
# 递归后-> 2
# 递归后-> 3
# 递归后-> 4
# 递归后-> 5