递归和分治

递归

高级语言中，函数自己调用和调用其他函数并没有本质的不同，我们把一个直接调用自己或者通过一系列调用语句间接地调用自己的函数，称作递归函数。（ps：每个递归定义必须至少有一个条件，当满足这个条件时递归不再进行，即函数不再调用自身而是返回值）

斐波那契(Fibonacci)数列

如果说兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。假设所有兔子都不会死去，能够一直干下去，那么一年以后可以繁殖多少对兔子呢？

代码实现：

int Fib(int i)
{
    if( i < 2 )
        return i == 0 ? 0 : 1;
    return Fib(i-1) + Fib(i-2);
}

分治

在遥远的周朝，人们受生产力水平所限，无法管理庞大的土地和众多的人民，因此采用了封邦建国的封建制度，把土地一层一层划分下去，以达到分而治之的目的，这也许是最古老的分治法了：

汉诺塔问题

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

public class Hanoi {
    /**
    * 
    * @param n 盘子的个数
    * @param a 原来的柱子
    * @param b 中间辅助柱子
    * @param c 最终到达的目标珠子
    */
    public void hanoi(int n, char a, char b, char c) {
        if (n == 1) {
            move(a, c);
        } else {
        	  //将n-1个盘子从a利用c移动到b盘子
            hanoi(n - 1, a, c, b);
            //将第n个盘子从a移动到c
            move(a, c);
            //将n-1个盘子从b利用a移动到c
            hanoi(n - 1, b, a, c);
        }
    }
 
    // 移动盘子
    private void move(char origin, char target) {
        System.out.println("方向:" + origin + "--->" + target);
    }
 
    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        hanoi.hanoi(3, 'A', 'B', 'C');
    }
}

快速排序

找出第n大的值

直尺

八皇后问题