🎞递归

递归（Recursion）就是函数在运行过程中调用它自己。但要给自己一个停下来的条件。

递归函数通常包含两部分：

1. 基例（Base Case）：递归的结束条件。没有它，递归会无限调用下去，直到程序崩掉（栈溢出）。
2. 递归调用（Recursive Call）：函数在某个条件下调用自己，把问题规模缩小。

递归的结构模板：

def recursive_function(参数):
    # 1. 基例（出口条件）
    if 满足结束条件:
        return 结果
    
    # 2. 递归调用（不断缩小问题规模）
    return recursive_function(缩小后的参数)

📌 ：每一次递归调用，问题的规模必须比上一次小，直到触碰到基例。

一、阶乘

阶乘（Factorial）是数学里一个非常基础但很重要的运算。 它的定义很简单：

$$n!=n\times (n-1)\times (n-2)\times \cdots \times 2\times 1$$

特殊约定：0的阶乘为1

1. 迭代实现

def factorial_iter(n: int) -> int:
    """
    计算 n!（迭代）
    约束：n 必须是非负整数
    """
    if n < 0:
        raise ValueError("n 必须是非负整数")
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iter(5))  # 120

2. 递归实现

def factorial_rec(n: int) -> int:
    """
    计算 n!（递归示例）
    注意：递归深度可能受限（Python 默认递归深度约 1000）
    """
    if n < 0:
        raise ValueError("n 必须是非负整数")
    if n == 0:
        return 1
    return n * factorial_rec(n - 1)

print(factorial_rec(5))  # 120

3. 阶乘的和的计算

阶乘的和（Sum of factorials） 求 1! + 2! + 3! + ... + n! 的值。 这个例子用递归计算阶乘的同时，再递归求和。

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

def sum_factorials(n):
    if n == 1:  # 基例
        return 1
    return factorial(n) + sum_factorials(n - 1)  # 当前阶乘加上前面阶乘的和

print(sum_factorials(5))  # 1!+2!+3!+4!+5! = 153

二、 栈

栈（Stack）是一种**后进先出（LIFO, Last In First Out）**的数据结构。

• 像一摞盘子：最后放上去的盘子，最先被拿走。
• 只能在“栈顶”添加（push）或移除（pop）元素。

1. 函数调用栈

• Python 在运行函数时，会用一个调用栈（Call Stack）记录每个函数的执行状态。
• 递归本质上就是函数调用栈的不断压栈（调用）和出栈（返回）。

2. 栈和递归的关系

• 每次调用函数，Python 会把这个函数的局部变量、返回位置等信息压入调用栈。

• 当函数结束时，这个栈帧会被弹出，回到上一个函数的执行位置。

• 递归的执行过程，就是“栈不断往下压 → 碰到基例 → 一层层弹出返回”的过程

def countdown(n):
    if n == 0:
        print("Boom!")
        return
    print(n)
    countdown(n - 1)
    print(f"返回到 {n}")

countdown(3)

调用栈变化：

push countdown(3)
push countdown(2)
push countdown(1)
push countdown(0)  # 触发基例
pop countdown(0)
pop countdown(1)
pop countdown(2)
pop countdown(3)

三、斐波那契数列（Fibonacci sequence)

神奇的斐波那契数列 #斐波那契数列 #兔子数列 #黄金分割数列 - 抖音

• 斐波那契数列由意大利数学家 列昂纳多·斐波那契（Leonardo Fibonacci）命名，他生活在公元12世纪。
• 斐波那契在他的著作《算经书》（Liber Abaci，1202年）中首次提出了这个数列，用来解决一个著名的兔子繁殖问题。(一对新生的兔子，从第二个月开始每个月都会生一对兔子。问第 n 个月末兔子的总对数是多少？)

斐波那契数列是这样一串数：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

每一项都是前两项之和：

• 定义：

$$F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2},n\ge 2$$

1. 递归思路

斐波那契的递归就是直接按照定义写：

• 如果 n 是 0 或 1，直接返回 n（基例）
• 否则，递归调用计算 fib(n-1) 和 fib(n-2)，然后相加

2.代码示例

def fib(n):
    if n == 0:  # 基例1
        return 0
    elif n == 1:  # 基例2
        return 1
    else:
        return fib(n - 1) + fib(n - 2)  # 递归调用

print(fib(7))  # 输出 13

3. 递归调用过程示意（fib(4)）

fib(4)
= fib(3) + fib(2)
= (fib(2) + fib(1)) + (fib(1) + fib(0))
= ((fib(1) + fib(0)) + 1) + (1 + 0)
= ((1 + 0) + 1) + (1 + 0)
= 2 + 1
= 3

• 斐波那契递归调用很多重复计算（比如 fib(2) 被算了两次），效率很低，时间复杂度是指数级 O(2^n)。
• 适合用来说明递归原理，但不适合大数据量直接用。
• 后续可以介绍动态规划或缓存优化（memoization），提高效率。

4. 用递归优化

memo = {0: 0, 1: 1}  # 预存基例结果

def fib_memo(n):
    if n in memo:
        return memo[n]
    memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

print(fib_memo(30))  # 迅速输出结果

四、汉诺塔

1. 游戏规则

有三根柱子，编号通常是 A、B、C。

第一根柱子上有 n 个不同大小的圆盘，盘子从上到下按大小递减叠放（小盘在上，大盘在下）。

目标是将所有圆盘从柱子 A 移动到柱子 C。

规则限制：

1. 每次只能移动一个盘子。
2. 任何时候，大盘不能放在小盘上面。

2. 递归思路

假设有 n 个盘子，目标是从柱子 A 移到柱子 C，用柱子 B 作为辅助柱。

1. 递归目标： 把最上面 n-1 个盘子从 A 移到 B，借助 C。
2. 移动第 n 个（最大）盘子： 把第 n 个盘子从 A 移到 C。
3. 递归目标： 把 n-1 个盘子从 B 移到 C，借助 A。

3. 程序实现

def hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"把盘子从 {source} 移动到 {target}")
        return
    # 先把上面 n-1 个盘子从 source 移到 auxiliary
    hanoi(n - 1, source, target, auxiliary)
    # 把第 n 个盘子从 source 移到 target
    print(f"把盘子从 {source} 移动到 {target}")
    # 把 n-1 个盘子从 auxiliary 移到 target
    hanoi(n - 1, auxiliary, source, target)

# 测试 3 个盘子的移动步骤
hanoi(3, 'A', 'B', 'C')