Java 方法递归

递归算法是一种直接或间接地调用自身的算法。

一个问题若满足以下三个条件往往都可以使用递归来解决：
1.递：这个原问题可以拆分为多个子问题的解。
2.拆分后的子问题和原问题除了数据规模不相同外，其他的解决思路完全相同。
3.归：存在递归的终止条件（或者一直递的条件）；

例如：利用递归方法计算10!
分析问题：看这个问题是否符合上述三个条件：
1. 10！可以拆分成 10 * 9!、9!=9 * 8!、8! = 8 * 7!…………；
2. 每个数的阶乘均为当前数n乘以(n-1)!；
3. 当n == 1时 n! = 1，则终止递归；
可以看出是满足的。
程序如下：

		public static void main(String[] args) {
		        int n = 10;
		        int ret = factor(n);
		        System.out.println("n的阶乘为：" + ret);
		}
    public static int factor(int n){
        if (n == 1){ // 终止条件
            return 1;
        }
        return n * factor(n - 1); // n!=n * (n-1)!
    }

注意：人脑不能同时想出那么多层，很容易让自己绕进去，所以写递归方法时只用关心这个方法的语义（即这个方法的作用），在合适的时机调用即可。
可以多画画图或者调试来理清递归的过程。

1 按顺序打印一个数字的每一位(例如 1234 打印出 1 2 3 4)

		public static void main(String[] args) {
		        int n = 1234;
		        printSingle(n);
	  }
    public static void printSingle(int n){
    		 // 递：num还不知道到底是几位数，先递出去
    		 // n > 9即一直递的条件
        if (n > 9){ 
            // 此时num一定不是个位数
            printSingle(n / 10);
        }
     	 // 归：当num递为一个个位数时开始输出
        System.out.println(n % 10);
    }

2 写一个递归方法，输入一个非负整数，返回组成它的数字之和。

    public static void main(String[] args) {
        int num = 1234;
        int ret = sumNum(num);
        System.out.println(ret);
    }
    public static int sumNum(int num){
        // 终止条件：当num为个位数时返回num
        if (num < 9) {
            return num;
        }
        // ret = num + num丢弃个位数后的各个位上的数字之和
        return (num % 10) + sumNum(num / 10);
    } 

3 计算斐波那契数列的第n项

斐波那契数列：斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*），即这个数列从第3项开始，每一项都等于前两项之和

    public static void main(String[] args) {
			 int ret = fib(0);
        System.out.println(ret);
     }
    public static int fib(int n){
        if(n == 0){
            return 0;
        }else if(n == 1 || n == 2) {
            return 1;
        }
        return fib(n - 1) + fib(n - 2);
    }
        

当n = 40时会发现运算很慢，是因为利用递归计算斐波那契数列中的值，尤其是n比较大时，会进行大量的重复运算，拖慢程序运算的速度。并且当n 增大时递归是呈指数级增长的。
这是n = 5时的大致递归过程，已经可以看出以上问题：

改善：可以使用循环的方式来求斐波那契数列问题，避免出现冗余运算。

     public static void main(String[] args) {
			 int ret = fib(0);
        System.out.println(ret);
     }
     public static int fib2(int n) {
        int last2 = 1;
        int last1 = 1;
        int cur = 0;
        if(n == 0){
            return 0;
        }else if(n == 1 || n == 2){
            return 1;
        }else {
            for (int i = 3; i <= n; i++) {
                cur = last1 + last2;
                last2 = last1;
                last1 = cur;
            }
            return last1;
        }

4 一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。

    public static void main(String[] args) {
        int n = 5;
        System.out.println("青蛙跳上一个" + n + "级的台阶总共有" + function(n) + "种跳法");
    }
    public static int function(int n) {
        // 终止：最终只剩1个或2个台阶
        if (n == 1) { // 剩余一个台阶时只有跳一个1种跳法
            return 1;
        }else if (n == 2) { // 剩余两个台阶时可以选择一次跳一种个或两个2种跳法
            return 2;
        }else {
        		// 当台阶数大于2时，青蛙第一次可以选择跳一个或两个，则剩余的n -1个或n -2个的跳法可以交给专门计算跳法的function（）方法去计算，加起来就好。（不用过分关注递归过程，关注函数语义）
            return function(n -1) + function(n -2);
        }
    }

5 递归求解汉诺塔问题
题目介绍：大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。
大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。
并且规定，任何时候，在小圆盘上都不能放大圆盘，且在三根柱子之间一次只能移动一个圆盘。
题目分析：假设n为总盘子数
n=1时最少移动总次数为1 n=2时最少移动总次数为3

n=3时最少移动次数为7

………………
则可以发现n个盘子的最少移动次数为2^n-1
分解：
①移动中，最中间一步，也就 第2^(n-1)步， 是将 最大的盘子 从第一根柱子移动到第三个柱子上，用move(A, C)进行移动（注意这里的第一根柱子、第三根柱子只是相对而言，根据移动过程不同会不断变化）；
②前2^(n-1)-1步可以看做是将上面的 n-1个盘子 借助 第三根柱子 从第一根柱子移动到了第二根柱子上， 此时就又是一个新的盘子数近似减半的汉诺塔问题，调用hanNo(n-1, A, C, B)解决；
③在2^(n-1) 步后的 2^(n-1)-1步可以看作是将 n-1个盘子 借助 第一根柱子 从第二根柱子移动到了第三根柱子上，同样又是一个新的盘子数近似减半的汉诺塔问题，调用hanNo(n-1, B, A, C)解决；

    static int step = 0; // 设置全局变量记录共走了多少步
    public static void main(String[] args) {
        System.out.println("5个盘子的移动方法为：");
        hanNo(5, 'A', 'B', 'C');
        System.out.println("n总共走了" + step + "步");
    }
// 假设A、B、C分别为第一、二、三个柱子，n表示总盘子个数，展示移动的过程
    public static void hanNo(int n, char A, char B, char C) {
        // 终止条件，当只有一个盘子时直接从A->C
        if (n == 1) {
            move(A, C);
        } else {
            // 前2^(n-1)-1步，将n-1个盘子从A->B,借助于C
            hanNo(n-1, A, C, B);
            // 中间步，最大盘子的移动
            move(A, C);
            // 后2^(n-1)-1步，将n-1个盘子从B->C,借助于A
            hanNo(n-1, B, A, C);
        }

    }
    // 当前最大盘子从A->C的移动
    public static void move(char A, char C) {
        System.out.print(A + "->" + C + " ");
        step++;
    }