递归

具体数学第一章通过三个例子由易到难给我们描绘了递归的思想。

汉诺塔

给定$n$个圆盘组成的塔，圆盘按照大小递减的方式套在三根柱子中的一根上。要求移动的过程中较大的圆盘不能放置在较小的圆盘上，求最优解法次数。

我们引入如下记号：
${T_n}$：将$n$个圆盘从一根柱子移动到另一根的最少移动次数，显然${T_0=0,T_1=1}$
移动3个圆盘的获胜思路，是首先将两个圆盘移动到中间，然后移动第三个圆盘，最后再移动剩下的两个放到它上面。
同理，我们可以将这种思想推理到$n$：
首先把$n-1$个小的圆盘移动到一个不同的柱子上，需要$T_{n-1}$次移动
然后移动最大圆盘，需要1次
最后再把那$n-1$个小圆盘移到最大圆盘上，需要$T_{n-1}$次移动。
这样最多需要$2T_{n-1}+1$次，即

$${T_n}{\quad}{\leq}{\quad}{2T_{n-1}+1} ,(n>0)$$

同时我们从里一个方面思考：
我们迟早必须移动最大的那个圆盘，当我们做这步时，那$n-1$个小圆盘已经在某根柱子上了，说明我们已经至少花了$T_{n-1}$次移动，如果不是最优移动，我们移动最大盘的时候可能会多于1次，移动完最大盘之后，还需要把剩下的$n-1$个圆盘移到最大盘之上，也需要$T_{n-1}$次移动，从而我们得到

$${T_n}{\quad}{\geq}{\quad}{2T_{n-1}+1} ,(n>0)$$

结合起来，我们得到递归式：

$$T_0=0 \\ T_n=2T_{n-1}+1,(n>0)$$

经过找规律我们可以得到最终的表达式：

$$T_n=2^n-1,(n\geq0)$$

我们可以用数学归纳法简单证明它是正确的
由$T_0=2^0-1$，假设$T_{n-1}$成立，对$n>0$时
$T_n=2T_{n-1}+1=2(2^{n-1}-1)+1=2^n-1$

平面上的直线

直线划分区域

每次增加一条直线，最多增加$n-1$个交点，也就是$n$个区域
即$L_0=1，L_n=L_{n-1}+n$
根据递归式累加求和可得最终结论$L_n=\frac{n(n+1)}{2}+1，n\geq0$

折线划分区域

推法一：
每次增加折线，相当于将$2$倍的直线交叉相消，也就是每个折线看成是两条直线，但是少了一半。因此每一条折线比两条直线分割的面的部分少$2$。
即$Z_n=L_{2n}-2n=2n^2-n+1，n\geq0$
推法二：
交点决定了射线和线段的条数，进而决定了新增的区域数。当有$n-1$条折线时，假设区域数为$Z_{n-1}$。为了使增加的区域最多，则折线的两边的线段要和$n-1$条折线的边，即$2(n-1)$条线段相交。线段数也就增加$4(n-1)$，区域数也就增加$4(n-1)+2$，但要注意的是，折线本身相邻的两线段只能增加一个区域。所以最终的区域增加数为$4n-3$。
所以递推式为
$Z_n=Z_{n-1}+4n-3$ 化简的最终结果也和上面一样。

斜线划分区域

约瑟夫环

从围成标有记号$1$到$n$的圆圈，每隔一个删去一个人，求最后留下来的是几号。

首先我们分奇偶性考虑得出一下两个结论：

偶数时：留下奇数序号下的人，场上人数缩小一半，变为奇数
偶数是：留下出来1之外的奇数序号下的人，场上人数缩小一半，变为偶数

第二点我们可以发现新下标编号和老下表编号的关系(见下图蓝红色下标)：

$f_{old}=2f_{new}-1$, 场上人数为偶数变为奇数时
$f_{old}=2f_{new}+1$, 场上人数为奇数变为偶数时

结合以上两点，我们可以根据初始编号以及人数反推回原始编号，从而得出递归表达式：

$J_1=1$
$J_{2n}=2J_{n}-1，n\ge1$
$J_{2n+1}=2J_{n}+1，n\ge1$

递归代码：

    public static Integer ans = 1;
    public static Integer Joseph(Integer n){
        if(n == 1){
            return ans;
        }else{
            if(n % 2 == 0){
                ans = 2 * Joseph(n / 2) - 1;
            }else{
                ans = 2 * Joseph(n / 2) + 1;
            }
        }
        return ans;
    }

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$J_{n}$	1	1	3	1	3	5	7	1	3	5	7	9	11	13	15	1

同时我们可以进一步求出递推式：

$n=2^m+l$
$J(2^m+l)=2l+1,m{\ge}0,0{\le}1<2^m$

再更近一步从位运算的角度思考：

$n=(b_mb_{m-1}{\cdots}b_1b_0)_2$
由$n=2^m+l$得$b_m$位为1，即：
$n=(1b_{m-1}{\cdots}b_1b_0)_2$
$l=(0b_{m-1}{\cdots}b_1b_0)_2$
$2$倍对应位运算中左移一位
$2l=(b_{m-1}{\cdots}b_1b_00)_2$
$2l+1=(b_{m-1}{\cdots}b_1b_01)_2$
$J(n)=(b_{m-1}{\cdots}b_1b_0b_{m})_2$
也就是最终证明了：
$J((b_mb_{m-1}{\cdots}b_1b_0)_2)=(b_{m-1}{\cdots}b_1b_0b_{m})_2$
也就是$n$向左循环移动一位得到$J_n$

Q.E.D.