递归

什么叫递归：自己调用自己，直到满足一个条件结束自己调用自己的过程

关键：

1.递归出口

2.逐步向出口逼近

入门案例：求1+2+3+...+100的和

通过循环实现

package com.tohka.demos;
//入门案例：求1+2+3+...+100的和
public class Demo1 {
    public static void main(String[] args) {
        System.out.println(getSum(100));
    }

    //循环实现
    public static int getSum(int number) {
        int sum = 0;
        for (int i = 1; i <= number; i++) {
            sum += i;
        }
        return sum;
    }
}

通过递归实现

package com.tohka.demos;
//入门案例：求1+2+3+...+100的和
public class Demo1 {
    public static void main(String[] args) {
        System.out.println(getSum(100));
    }

    //递归实现
    public static int getSum(int number) {
        int sum = 0;
        if(number == 1) { //递归出口
            return 1;
        } else {
            return number + getSum(number -1); //向出口逼近
            //  假设传递的参数为4
            //  getSum(4) = 4 +getSum(3)
            //            = 4 + 3 +getSum(2)
            //            = 4 + 3 + 2 +getSum(1)   getSum(1)达到递归出口结果为1
            //  getSum(4) = 4 + 3 + 2 + 1 = 10
        }
    }
}

拓展拔高：斐波拉契数列之兔子案例

一对兔子从第三个月开始下一对小兔子，然后以后每个月都下一对，假设兔子长生不死

并且他们的崽子也是一样的去下小兔子，问N个月以后一共有多少对兔子？用递归实现

分析：

1	第一个月                                  |
1	第二个月							      |
2	第三个月                                  |                   |
3	第四个月    |                             | 				  |
5	第五个月	|                      |      |                   |         |
8	第六个月    |     |       |        |      |             |     |         |
13
21
。
。
。
找到规律：斐波拉契数列：1 1 2 3 5 8 13 21......

代码实现

实现思路：

1.找到规律：从第三个月开始，后面一个月兔子数量等于前两个月之和

2.找到递归出口：第一个月、或者第二个月

3.逼近出口:当前月份前两个月兔子之和

package com.tohka.demos;
//一对兔子从第三个月开始下一对小兔子，然后以后每个月都下一对，
//假设兔子长生不死 并且他们的崽子也是一样的去下小兔子，
//问N个月以后一共有多少对兔子？用递归实现
public class Demo2 {
    public static void main(String[] args) {
        System.out.println(getSum(5));
    }

    public static int getSum(int month) {
        if(month == 1 || month ==2) {  //递归出口
            return 1;
        } else {
            //逼近递归出口
            return getSum(month-1) +getSum(month -2);

            //假设求第五个月的兔子
            //getSum(1) = 1; getSum(2) =1 都是递归出口
            //getSum(5) = getSum(4) + getSum(3)
            //          = getSum(3)+ getSum(2)   +   getSum(2) + getSum(1)
            //          = getSum(2)+ getSum(1) +getSum(2) +   getSum(2) + getSum(1)
            //getSum(5) = 1+1+1+1+1 = 5
        }
    }
}

BAT笔试真题

使用java递归解决汉诺塔问题

参考博客

https://blog.csdn.net/Hurricane_m/article/details/89043699