1、概念

程序调用自身的编程技巧称为递归（recursion）。

递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，
它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。

递归的能力在于用有限的语句来定义对象的无限集合。

一般来说，递归需要有边界条件、递归前进段和递归返回段。
当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

2、执行特点

1. 调用自己一次的情况：调用位置前面的代码是正循环，调用位置后面的代码是反循环。

2. 调用自己两次的情况：他是一个二叉树的遍历过程（例如：汉诺塔算法：中序遍历）。

看下图解：

1.jpg

汉诺塔算法（中序遍历）

2.jpg

3、给出一些常规的递归的代码

/**
 * 遍历一个数字
 */
public void fun(int n) {
    System.out.println(n);
    if (n < 0) {
        return;
    } else {
        fun(n - 1);
        System.out.println(n);
    }
}

/**
 * 阶乘算法
 * 1*2*3*4*5....     n!
 * 5!  = 5*4!      4! =  4*3!
 */
public int fact(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * fact(n - 1);
    }
}

/**
 * 斐波那契数列算法
 * fibonacciSequence数列   8=7+6   7=6+5  6=5+4
 * 1   1  2  3  5  8   13  21  34  55  89  144......
 * 返回第n项
 */
public int fibonacciSequence(int n) {
    if (n == 1 || n == 2) {
        return 1;
    } else {
        return fibonacciSequence(n - 1) + fibonacciSequence(n - 2);
    }
}

/**
 * 汉诺塔算法：中序算法
 *
 * @param n      盘子的个数
 * @param start  开始的柱子
 * @param middle 中介柱子
 * @param end    结果柱子
 */
public static void hanoi(int n, int start, int middle, int end) {
    if (n <= 1) {
        System.out.println(start + "----->" + end);
    } else {
        hanoi(n - 1, start, end, middle);
        System.out.println(start + "----->" + end);
        hanoi(n - 1, middle, start, end);
    }
}

4、测试及结果

@Test
public void main() {
    fun(3);
    System.out.println();
    System.out.println("----------------------");
    System.out.println("阶乘：" + fact(5));
    System.out.println("------fibonacciSequence-----");

    for (int i = 1; i < 9; i++) {
        System.out.print(fibonacciSequence(i) + "  ");
    }

    System.out.println();

    System.out.println("fibonacciSequence(8) = " + fibonacciSequence(8));
    System.out.println("----------- 汉诺塔算法 -----------");
    hanoi(3, 1, 2, 3);
}

结果：
3  2  1  0  -1  0  1  2  3  
----------------------
阶乘：120
------fibonacciSequence-----
1  1  2  3  5  8  13  21  
fibonacciSequence(8) = 21
----------- 汉诺塔算法 -----------
1----->3
1----->2
3----->2
1----->3
2----->1
2----->3
1----->3