🧮 CSC3001 LEC8-10 递归

(涵盖第 5 个讲义)

LN5 Recursion 递归

递归是数学归纳法的底层逻辑，也是 coding 中的常用手段。


递归思想

集合的幂集基数

对于 Sn = {a1, a2,…, an}，求 |pow(Sn)| 的递推式? S1 = {ø, {a1}}, S2 = {ø, {a1}, {a2}, {a1, a2}} …… 所以 Sn+1 含有所有 Sn 含有的元素，以及这些元素与 an+1 的并集：(Se 表示 S 的各个元素)$$S_{n+1}={{Se_n, Se_n∪{a_{n+1}}}}$$ 所以 |pow(Sn+1)| = 2|pow(Sn)|


没有“111”的二进制数

对于 n 比特的，不存在“111”结构的二进制数 Bn 的数量的递推式？ B1：{1, 0} →2 B2：{10, 01, 11, 00} →4 B3：{110, 000, 010, 011, 001, 100, 101} →7 B4：{1100, 0011, 1011, 1101, 0000, 1000, 0001, 0101, 1010, 0100, 0110, 0010, 1001} →13 …… 观察 B4 中的元素：

  • {0110, 0000, 0010, 0011, 0001, 0100, 0101} 从 3 中得到，全部都可以左加一位 0 {1010, 1001, 1011, 1000} 从 2 中得到，全部可以左加两位 10 {1101, 1100} 从 1 中得到，全部可以左加三位 110
  • 也可以理解为 “B3 中都可以加一位 0，但所有在最高两位不是 11 的才可以加一位 1” 所以 |Bn| = |Bn-1| + |Bn-2| + |Bn-3| (n>3)


递归解题

核心思想：大则化小、多则归一、分而化之


汉诺塔(河內塔)

三个柱子，n 个在最左侧从大到小叠起来的圆盘。要在保持每根柱子上都是大盘子在小的下面的前提下，把最左侧的盘子原封不动的呈现在最右侧，需要多少步 f(n) ？

  • 为了简洁，我们把最小的盘子 叫做 1，最大的叫做 n；柱子依次叫做 a, b, c：

  • n=1: 1->c

  • n=2: 1->b、2->c、1->c

  • n=3: 1->c、2->b、1->b、3->c、1->a、2->c、1->c

观察 n=3，可以简单理解为：先将较小两盘移开，把最大盘移到最右边，再移动较小两盘到最右边。中间那部等价于 n=1；而前后三步本质上都是想将两个圆盘(不变顺序)移到另个柱子(“从 a 到 b” 和 “从 b 到 c”)。不难发现 n=2 的目的 恰好也是类似的 “从 a 移到 c”。**因为三个柱子没有“独特性”，故无论从哪移到哪，圆盘数相同时，步骤数一定相同。**所以解析 f(3) 可以 依次调用 f(2)、f(1)、f(2)。 所以我们可以猜测 f(3) = 2f(2)+1，推至 f(n) = fS(n-1)+1，如下图所示。

按上述逻辑，任何情况下汉诺塔问题都可以递归进行“三分拆解”，最后剩下一系列单次移动。所以我们基本上只需要定义单次移动方法、三分递归方法、递归入口方法和主方法就可以写出 Python 的解法：

def move(src: list[int], tar: list[int], name_src: str, name_tar: str, steps: list[int], A, B, C):
    # 移动一个圆盘，并打印当前状态
    pan = src.pop() # 记录并去掉 source 数组顶部的元素
    tar.append(pan) # 将其加到 target 数组
    steps[0] += 1
    print(f"第 {steps[0]} 步: {name_src} -> {name_tar}")
    print(f"A={A}, B={B}, C={C}\n")

def dfs(i: int, src: list[int], buf: list[int], tar: list[int], # 递归 f(i)
        name_src: str, name_buf: str, name_tar: str,
        steps: list[int], A, B, C):
    if i == 1:
        move(src, tar, name_src, name_tar, steps, A, B, C)
        return
    dfs(i - 1, src, tar, buf, name_src, name_tar, name_buf, steps, A, B, C)  # f(i-1)
    move(src, tar, name_src, name_tar, steps, A, B, C)  # f(1)
    dfs(i - 1, buf, src, tar, name_buf, name_src, name_tar, steps, A, B, C)  # f(i-1)

def solve_hanota(A: list[int], B: list[int], C: list[int]):
    # 求解并返回总步数
    n = len(A)
    steps = [0]
    dfs(n, A, B, C, "A", "B", "C", steps, A, B, C)
    return steps[0]

if __name__ == "__main__":
    num = int(input("请输入汉诺塔圆盘数量："))  # 注意 input 自动存储为 type:str
    A = list(range(num, 0, -1))  # [num, num-1, ..., 1]
    B = []  # 也可以写 list[int]
    C = []
    total_steps = solve_hanota(A, B, C)
    print(f"共移动了 {total_steps} 步。")

卡塔兰数(Catalan Numbers)

用 n 组正反斜杠可以组成多少种“山脉”图？(不能低于基准线)合法的“山脉”比如：

记递推式为 m(n)，观察后发现，所有山脉的 “顶部” 都是 “/\" 结构。我们不妨将山分为两个组分：“U”:山腰，和 “E”:山顶 ( “/\" 结构) 。比如图中 n=3 可以抽象为 EEE, EUE, UEE, UEE和UUE。我们可以用二分法将其理解为一部分”在 U 上的“ 和 剩余部分”自由分配的“：

1、“E …剩余 n-1 项…”：m(0) x m(n-1)

2、“U一项…剩余 n-2 项…”：m(1) x m(n-2)

3、“U两项…剩余 n-3 项…”：m(2) x m(n-3)

k、“Uk-1项…剩余 n-k 项…”：m(k-1) x m(n-k)

$$所有情况加起来就是 ”卡塔兰数“：m(n) = \sum_{k=1}^{k=n} m(k-1) \times m(n-k)$$

$$又记作：Catalan_n = \frac1{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!,n!}$$



解递推式

一元线性递推展开公式

  • 齐次线性递推式(一次项系数≠1)：$$a_k=r a_{k-1}\ \to\ a_k=r^{k-1}a_1$$
  • 非齐次基准线性递推式(一次项系数=1)：$$a_k = a_{k-1} + b\ \to\ a_k = a_1 + (k-1)b$$
  • 非齐次线性递推式(一次项系数≠1)如汉诺塔：$$a_k=r a_{k-1}+b\ \to \ a_k=r^{k-1}a_1+\frac{b,(r^{,k-1}-1)}{r-1}$$

一元非线性(二分法)递推式

对于二分法的递推式 a2k = mak+nk+c：(C 是用首项带进去算出来的常数)

  • 一般解(m\neq 1,2)：$$a_{2k} = C·2k^{log_2m} + \frac{n}{2-m},2k + \frac{c}{1-m}$$
  • 特殊情况 m=2：$$a_{2k} = C·2k + nklog_22k - c$$
  • 特殊情况 m=1：$$a_{2k} = a_1 + n(k-1) + ct$$

比如对于归并排列 a2k = 2ak+2k = 2klog2(2k)


母函数解法

对于用 a 表示的数列的一次递推式，通式比如： $$a_{n} = c_{n-1}·a_{n-1} + c_{n-2}·a_{n-2},\ n≥2$$

可以假设其母函数为： $$F(x) = \sum_{n=2}^{\infty} a_nx^n$$

那么用母函数表示递推式就是：$$F(x)-a_0-a_1x=c_{n-1}x·(F(X)-a_0)+c_{n-2}x^2·F(x)$$

所以可以表示出：$$F(x)={{a_0+a_1x-a_0c_{n-1}x}\over{1-c_{n-1}x-c_{n-2}x^2}}$$

分解分母的二次函数，得到两个式子相加（两个分子先待定，再用原分子各项系数解出）

根据以下式子还原出母函数本体：$$\frac\beta{1-\alpha x}=\sum_{n=0}^{\infty}\beta·\alpha^n x^n$$

最后在母函数基础上去掉叠加符号和 an 就得到了数列的通式

comments powered by Disqus