🎞递归

递归（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$$

可以看到 $n$ 的阶乘就是从1到$n$的乘积。

特殊约定：0的阶乘为1。

设计一个函数来实现计算$n$的阶层并不复杂，通常我们可以使用递推的方式，及一步一步的计算，最后出它的乘积：

# 方法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

在这个程序中，n: int 是 Python 里的类型提示，他告诉人们参数n是一个整数，-> int同样是类型提示，他表示这个函数返回一个整数，不过这里只是提示，而非强制约束，程序员依然可以无视他传入其他的值，函数依旧会接收这个参数并开始工作，不过和可能不规范的操作会引起意外。

在递归这一章节，我们使用另外一种方式来实现这一功能。首先我们容易观察到，$5!=5\ast 4!$，$8!=8\ast 7!$，所以对于更一般的情况，有：

$$n!=n\ast (n-1)!$$

它的函数表达式可以写为：

$$f(n)=n\ast f(n-1)$$

程序示例：

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

print(factorial_rec(5))  # 120

二、斐波那契数列（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$$

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

• 如果 n 是 0 或 1，直接返回 n（基例）
• 否则，递归调用计算 fib(n-1) 和 fib(n-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

在这段简短的代码中，基例可以写成：

if n == 0 or n == 1:
    return n

它很好理解，当 fib(1)或者fib(0)的时候返会0或者1。令人容易困惑的是，我们在其他数值的时候也直接简单的返回fib(n - 1) + fib(n - 2) ，就好像程序自己能在知道fib(n - 1) ，fib(n - 2) 的值一样。事实确实如此，它知道，但是它不是直接知道。

假设现在 n 的值为 4，我们手写绘制他的调用的树形图：

                         fib(4)
                       /        \
                  fib(3)        fib(2)
                 /      \       /      \
             fib(2)    fib(1) fib(1)   fib(0)
             /    \
         fib(1)  fib(0)

我们发现，当调用fib(4)时，返回了 fib(3)+fib(2)，所以程序会首先调用fib(3)企图获取他的返回值，接着由于 fib(3)返回了fib(2)+fib(1)，由于fib(1)可以直接获取到1，所以它只需要调用fib(2)，最后计算得到 fib(2)的值为1。至此，函数fib(3)所以要的所有值计算完毕，函数终于获得了 fib(3)的值，由于 fib(4)返回的是 fib(3)+fib(2)，所以程序需要使用相同的方法，再次计算fib(2)。函数的调用过程虽然复杂，但是Python解释器会保证它按我们设计的逻辑运行。

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)$。

在上述的例子中，我们发现有一些数据被重复的计算了两次，所以对于计算过的数据，我们可以保存起来，当一个值检测到被计算过的时候，就直接使用之前计算的值：

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))  # 迅速输出结果

我们使用字典来存储数据，键值对的键表示被计算过的数，而他的值就是数据计算后的值。每一次斐波那契的计算，都检测一下n这个数是否被计算了，如果是就直接返回他的值，否则才进入计算。

我们称这种优化的方法为：记忆化。

TIP

阶乘示例中，它展开式是一个链条，这种我们称为线性递归，而像斐波那契数列这种，在一个函数里分别调用多次自己，我们称为树状递归（分支递归）。

三、整数分解问题

给出一个正整数 a，要求将它分解成若干个正整数的乘积：

$$a=a_1\times a_2\times a_3\times \cdots \times a_n$$

并且满足：

$$1<a_1\le a_2\le a_3\le \cdots \le a_n$$

问：这样的分解方式一共有多少种。

注意：

• 分解出来的因子必须大于 1。
• 因子的顺序不考虑区别，例如：$ 2 \times 4$ 和 $ 4 \times 2 $ 属于同一种，其中 $ n $ 也算一种分解方式。

例如数字 8 有三种分解方式：

• $8 = 2 \times 2 \times 2 $
• $8 = 2 \times 4 $
• $8 = 8 $

实现这一功能的递归程序如下：

ans = 0  # 保存分解方案数量

def factorization(x, min_factor = 2):
    global ans
    # x == 1，说明前面的因子已经乘出了原数字
    # 找到一种合法分解
    if x == 1:
        ans += 1
        return
    # 枚举当前可以选择的因子
    for i in range(min_factor, x + 1):
        if x % i == 0:
            factorization(x // i, i)

factorization(8)

print(ans)

方便理解这个程序，我们把函数的调用关系跟踪一遍：

fun(8,2)
├── fun(4,2)				# 选择因子 2，剩余 8/2=4
│   ├── fun(2,2)			# 选择因子 2，剩余 4/2=2
│   │   └── fun(1,2)		# 选择因子 2，剩余 2/2=1，结束：对应 2 * 2 * 2
│   └── fun(1,4)			# 选择因子 4，剩余 4/4=1，结束：对应 2 * 4
│
├── fun(2,4)				# 选择因子 4，结束：被过滤，否则要出现 4 * 2。
│
└── fun(1,8)				# 选择因子 8，剩余 8/8=1，结束：对于 8

再绘制出它的搜索递归树：

                         fun(8, 2)(cnt=0)
                    /        |        \
                  2          4          8
                  |          |          |
              fun(4,2)   fun(2,4)     end(cnt+=1)
               /    \
              2      4
              |      |
          fun(2,2)   end(cnt+=1)
             |
             2
             |
            end(cnt+=1)

这里面容易困惑的点是，既然是递归，那么min_factor不应该和第一次调用一样都是2吗？这样逻辑才是统一的，确实，正常情况下我们似乎可以直接省略第二个参数，而固定的写一个2，程序就变成下面这样:

ans = 0  # 保存分解方案数量

def factorization(x):
    global ans
    # x == 1，说明前面的因子已经乘出了原数字
    # 找到一种合法分解
    if x == 1:
        ans += 1
        return
    # 枚举当前可以选择的因子
    for i in range(2, x + 1):
        if x % i == 0:
            factorization(x // i)

factorization(8)

print(ans)

我们直接把min_factor省略，for循环的调用中直接使用数字2，但是发现运行后输出的结果为：4。此时绘制他的调用图：

fun(8)
├── fun(4)                   # 选择因子 2，剩余 8/2=4
│   ├── fun(2)               # 选择因子 2，剩余 4/2=2
│   │   └── fun(1)           # 选择因子 2，剩余 2/2=1
│   │                        # 对应：2×2×2
│   └── fun(1)               # 选择因子 4，剩余 4/4=1
│                            # 对应：2×4
│
├── fun(2)                   # 选择因子 4，剩余 8/4=2
│   └── fun(1)               # 如果允许继续选择更小因子2
│                            # 对应：4×2（与2×4重复）
│
└── fun(1,8)                 # 选择因子 8，剩余 8/8=1
                             # 对应：8

这里多出了一次，这是因为我们失去了第二个参数的限制作用，导致 4 * 2 这种情况被分解一次，但是题意要求 2 * 4 和他只能算一种情况。

四、汉诺塔

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')