递归
具体数学第一章通过三个例子由易到难给我们描绘了递归的思想。
汉诺塔
给定n个圆盘组成的塔,圆盘按照大小递减的方式套在三根柱子中的一根上。要求移动的过程中较大的圆盘不能放置在较小的圆盘上,求最优解法次数。
我们引入如下记号:
Tn:将n个圆盘从一根柱子移动到另一根的最少移动次数,显然T0=0,T1=1
移动3个圆盘的获胜思路,是首先将两个圆盘移动到中间,然后移动第三个圆盘,最后再移动剩下的两个放到它上面。
同理,我们可以将这种思想推理到n:
首先把n−1个小的圆盘移动到一个不同的柱子上,需要Tn−1次移动
然后移动最大圆盘,需要1次
最后再把那n−1个小圆盘移到最大圆盘上,需要Tn−1次移动。
这样最多需要2Tn−1+1次,即
Tn≤2Tn−1+1,(n>0)
同时我们从里一个方面思考:
我们迟早必须移动最大的那个圆盘,当我们做这步时,那n−1个小圆盘已经在某根柱子上了,说明我们已经至少花了Tn−1次移动,如果不是最优移动,我们移动最大盘的时候可能会多于1次,移动完最大盘之后,还需要把剩下的n−1个圆盘移到最大盘之上,也需要Tn−1次移动,从而我们得到
Tn≥2Tn−1+1,(n>0)
结合起来,我们得到递归式:
T0=0Tn=2Tn−1+1,(n>0)
经过找规律我们可以得到最终的表达式:
Tn=2n−1,(n≥0)
我们可以用数学归纳法简单证明它是正确的
由T0=20−1,假设Tn−1成立,对n>0时
Tn=2Tn−1+1=2(2n−1−1)+1=2n−1
平面上的直线
直线划分区域
每次增加一条直线,最多增加n−1个交点,也就是n个区域
即L0=1,Ln=Ln−1+n
根据递归式累加求和可得最终结论Ln=2n(n+1)+1,n≥0

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

斜线划分区域
约瑟夫环
从围成标有记号1到n的圆圈,每隔一个删去一个人,求最后留下来的是几号。
首先我们分奇偶性考虑得出一下两个结论:
偶数时:留下奇数序号下的人,场上人数缩小一半,变为奇数
偶数是:留下出来1之外的奇数序号下的人,场上人数缩小一半,变为偶数
第二点我们可以发现新下标编号和老下表编号的关系(见下图蓝红色下标):
fold=2fnew−1, 场上人数为偶数变为奇数时
fold=2fnew+1, 场上人数为奇数变为偶数时
结合以上两点,我们可以根据初始编号以及人数反推回原始编号,从而得出递归表达式:
J1=1
J2n=2Jn−1,n≥1
J2n+1=2Jn+1,n≥1

递归代码:
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 |
Jn |
1 |
1 |
3 |
1 |
3 |
5 |
7 |
1 |
3 |
5 |
7 |
9 |
11 |
13 |
15 |
1 |
同时我们可以进一步求出递推式:
n=2m+l
J(2m+l)=2l+1,m≥0,0≤1<2m
再更近一步从位运算的角度思考:
n=(bmbm−1⋯b1b0)2
由n=2m+l得bm位为1,即:
n=(1bm−1⋯b1b0)2
l=(0bm−1⋯b1b0)2
2倍对应位运算中左移一位
2l=(bm−1⋯b1b00)2
2l+1=(bm−1⋯b1b01)2
J(n)=(bm−1⋯b1b0bm)2
也就是最终证明了:
J((bmbm−1⋯b1b0)2)=(bm−1⋯b1b0bm)2
也就是n向左循环移动一位得到Jn
Q.E.D.