具体数学: 递归

递归问题分析

递归函数定义

• 递归被用于定义数学函数或归纳证明
• 递归的数学模型分为基础和递归两部分
• 通过递归证明命题被称为数学归纳法，以正确的最小命题为基础，分为递归基础、递归假设、递归步骤三部分

汉诺塔问题

• 问题描述：将n个从上到下大小依次递增的盘片将A柱借助B柱移到C柱，其中不允许大盘片在小盘片上，求解移动次数

• 问题分析：将n盘从A柱移到C柱，需先将n − 1盘通过C柱移到B柱，再将第n盘片直接移到C柱，然后将n − 1盘通过A柱移到C柱；若只剩一盘，则可直接移动

• 递归式：$\begin{cases}T(1)=1\\T(n)=2T(n-1)+1\end{cases}$，即移动两次n − 1盘，一次直接移动

• 通项式：T(n) = 2ⁿ − 1，可证明其是最优解

• 代码求解移动过程：

  ```c++ void RecursionSolution(int n, int from, int use, int to) { if (n == 1) { // from -> to directly cout << from << “->” << to << endl; return; } RecursionSolution(n - 1, from, to, use); cout << from << “->” << to << endl; RecursionSolution(n - 1, use, from, to); } int HanoiTower(int n) { RecursionSolution(n, 0, 1, 2); // 输出移动过程 return (1 << n) - 1; // 返回移动次数 }

直线划分平面问题

• 问题描述：用n条直线划分一个平面，求出能划出的最多的部分数

• 问题分析：S(0) = 1, S(1) = 2；n ≥ 2时，每次使其和剩下n − 1条直线都有交点，则划分部分最多

• 递归式：$\begin{cases}S(0)=1\\S(n)=S(n-1)+n\end{cases}$

• 通项式：$\begin{align}S(n)=\frac{n(n+1)}2+1\end{align}$

• 证明其必定能做到上述操作：将n − 1次划分后的交点用圆围起来，用直径l划分该圆，使交点平均地分布在圆的两部分(若交点数为奇数，则让l穿过一点后再平均分配)，则在l划分的两个部分中，这些直线在圆外是不相交(交点在圆内)且不为同一直线(同一直线被l划分在其两边)，平移l至圆外，则必定能交到n − 1个交点

• 推广：平面角划分平面问题

  分析：使角始终处于上次划分后区域最大的部分，延长角的两条射线，则转换为2n条直线划分平面问题

  递归式：𝒮(n) = S(2n) − 2n

  通项式：𝒮(n) = 2n<sup>2</sup> − n + 1

• 圆划分平面问题：

  每增加一个圆，新增圆与其余所有圆都相交且有两个交点，新增部分数目与新增交点数目相同，即：

  $T_n=\begin{cases}2,&n=1\\T_{n-1}+2(n-1),&n>1\end{cases}$ 因此$\begin{align}T_n=T_1+2\sum_{i=1}^{n-1}i=2+n(n-1)\end{align}$

约瑟夫问题

• 问题描述：使编号依次递增(编号从i开始)的人(共有n人)按顺序围成一圈，每m次报数后踢出该人，求幸存者的编号

• 问题分析：要知道f(n,m)，就需要先知道f(n−1,m)，但后者从i开始，为了使前者能转换成后者，每次踢出后，需要找出其编号对应关系，若用[k]表示下一轮报数从k开始，则：$\begin{cases}f(n,m)踢出一人:i,i+1,\cdots,i+m-2,[i+m],\cdots,i+n\\f(n-1,m):[i],i+1,\cdots,i+n-1\end{cases}$

  当i = 0时，可找到对应关系：f(n,m) = f(n−1,m)% n

  使[]括起的编号一一对应后，可找到如下关系：f(n,m) = (f(n−1,m)+m−i)% n + i

  其中i为偏移量，减去i即转换成编号从0开始的情况，最后加上i得到原问题从i开始的情况

  上述情况假设m < n，实际上m ≥ n的情况下，踢出一人后报数从i + (m% n)开始，因模运算的性质也满足上述递归式

• 递归式：$\begin{cases}f(1,m)=i\\f(n,m)=(f(n-1,m)+m-i)\%\ n+i\end{cases}$，从i开始编号

  若要求从j(i≤j≤i+n)开始报数，可先求从i开始报数，然后增加j − i(注意模n)

• 递归求解代码：

  ```c++ int Solution(int n, int m, int i) { // 从i开始编号, 从i开始报数 return n == 1 ? i : (Solution(n - 1, m, i) + m - i) % n + i; } int Josephus(int n, int m, int i, int j) { // 从i开始编号, 从j开始报数 return (Solution(n, m, i) - i) % n + j - i; }

f(n,2)及推广的通项式求解

上述过程实际只给出了递归式，实际上当m = 2时，原问题是以下问题的一个特例：

• 给出递归式$\begin{cases}f(j)=\alpha_j,&0\lt j\lt m\\f(mn+j)=cf(n)+\beta_j,&0\le j\lt m,n>0\end{cases}$，求出f(x), x ∈ N<sup>+</sup>

• 清单法(猜证法)：即给定f(n)可能的形式，通过给定特定的f(n) = X(n)(要求X(n)能求出唯一对应的(α<sub>j</sub>,β<sub>j</sub>)值)，反过来推出f(n)中各系数的值

  容易得到，如果递推式中含k个变量，则至少需要找出k个上述函数

• 当m = c = 2时，即所谓f(n,2)，可很容易地找到三个函数：

  猜测

  令$f(n)=1,解得\begin{cases}\alpha_1=1\\\beta_0=\beta_1=-1\end{cases}$，即A − B − C = 1

  令$f(n)=n,解得\begin{cases}\alpha_1=\beta_1=1\\\beta_0=0\end{cases}$，即A + C = n

  令$f(n)=2^k(其中n=2^k+l),解得\begin{cases}\alpha_1=1\\\beta_0=\beta_1=0\end{cases}$，即A = 2<sup>k</sup>

  联立得$\begin{cases}A=2^k\\B=2^{k+1}-n-1=2^k-l-1\\C=n-2^k=l\end{cases}$，即f(n) = 2<sup>k</sup>α<sub>1</sub> + (2<sup>k</sup>−l−1)β<sub>0</sub> + lβ<sub>1</sub>

  • 当α<sub>1</sub> = 1、β<sub>0</sub> =  − 1、β<sub>1</sub> = 1时，正是f(n,2) = 2l + 1

• 很不幸，无法给出如此多的函数来使用清单法求出一般形式的通解，但能根据递推式给出如下关系：

  令n = (n)<sub>m</sub> = b<sub>k</sub>b<sub>k − 1</sub>⋯b<sub>0</sub>，每右移一位相当于取nm + j中的n，原本的末位则是j：

  $\begin{align}&f((n)_m)=cf((n)_m>>1)+\beta_{b_0}=c(cf((n)_m>>2)+\beta_{b_1})+\beta_{b_0}=\cdots\\&=c^kf(b_k)+c^{k-1}\beta_{b_{k-1}}+\cdots+c\beta_{b_1}+\beta_{b_0},其中b_k<m,故f(b_k)=\alpha_{b_k}\end{align}$

  因此对任何n，将其写成m进制，则f(n)等于(α<sub>bk</sub>β<sub>bk − 1</sub>⋯β<sub>b0</sub>)<sub>c</sub>

  当限定为约瑟夫问题f(n,2)时，f(n) = (n)<sub>2</sub>循环左移一位