递归

1)The Tower of Hanoi

$T_n$定义为，在规则下，把$n$个disk从一个peg移到另一个peg，另外两个peg里的任何一个。对$n+1$的时候，把最上面的$n$个看成一个整体，可得递归关系 $$ \begin{array}{l} T_0=0\\ T_n=2T_{n-1}+1\quad n > 0 \end{array} $$ 递归可以这样解，两边加1 $$T_n+1=2(T_{n-1}+1)$$ 2) 直线分平面

考虑加入第$n$条线的时候，最多能增加几个区域？
1. 增加的区域是把原来的某个区域一分为二，
2. 如果要分某个老区域，新的线必然至少要和这个区域的边界相交一次。
3. 如果交点是$k$个，那么新区域是$k+1$个，因为每个交点和一个老线相关，而每个老线必然是两个老区域的边界，这两个区域都被分了，但是有些老区域被计数两次，这些被计数两次的老区域的特点是他们的两个边界是和新线相交的老线，因为区域全是凸的，如果一条直线和一个凸区域的边界相交两次，那么必然只相交两次。对新线来说，和一个区域相交两次，这两个交点必然相邻(因为区域中间是没有老线的)，反过来所有相邻交点必然是和一个老区域交了两次。总之，$k$个交点，新区域的个数是$2k-(k-1)$。
4. 显然新加入一条线，交点最多有$n-1$个。

所以递归关系是 $$ \begin{array}{l} T_0=0\\ T_n=T_{n-1}+n\quad n > 0 \end{array} $$ 3) Josephus Problem

n个人围一圈，第一轮kill掉编号为2的倍数的人，重新编号第二轮再kill掉编号为2的倍数的人，直到只剩一个人，求这个人开始的编号。

递归是把原始问题通过某种变化转变成较小的同样描述的问题，然后找出两个问题解的关系，上面的问题自然的给出了大问题变小问题的过程

用$J(n)$记$n$个人中剩下的那个人的编号，第一轮过后，得到较小的问题$J(m)$记为这个人在第二轮里的编号，这个人在第一轮的编号，可以由$J(m)$算出可得两个问题的关系，但是n为奇数或者偶数的时候关系并不一样。 $$ \begin{array}{l} J(1)&=1\\ J(2n)&=2J(n)-1\\ J(2n+1)&=2J(n)+1 \end{array} $$ 解为 $$J(2^m+l)=2l+1$$ 这个关系有个性质：$2^m+l$的二进制表达，做循环左移得$2l+1$。

考虑一般的递归公式 $$ \begin{array}{l} f(1)&=\alpha\\ f(2n)&=2f(n)+\beta_0\\ f(2n+1)&=2f(n)+\beta_1 \end{array} $$ 先假设$f(n)$的表达式为 $$f(n)=A(n)\alpha+B(n)\beta_0+C(n)\beta_1$$ 4) 长度为n的三进制数，其中0的个数为奇数的个数

记这样的三进制数为$b_n$个,按最后一位的情况分类 $$b_n=b_{n-1}+b_{n-1}+(3^{n-1}-b_{n-1})$$