递归-斐波那契&兔子

aeolian 2021-08-08 原文

斐波那契数列

斐波那契数列的排列是：0，1，1，2，3，5，8，13，21，34，55，89，144……依次类推下去。

观察后发现，它后一个数等于前面两个数的和。在这个数列中的数字，就被称为斐波那契数。

递归思想：一个数等于前两个数的和。

package com.autumn;

/**
 * 斐波那契数列的排列
 * 0，1，1，2，3，5，8，13，21，34，55，89，144
 * 后一个数等于前面两个数的和
 */
public class Recursive {

    public static void main(String[] args) {
        for (int i= 0;i<30;i++){
            System.out.println(fib(i));
        }
    }

    /**
     * 斐波那契竖列返回的值
     * @param index 下标,从0开始
     * @return 下标对应的值
     */
    public static int fib(int index){
        /*如果下标是0,返回0*/
        if (index == 0){
            return 0;
        }
        /*如果下标是1,返回1*/
        if (index ==1){
            return 1;
        }
        //否则,返回前两项的和
        return fib(index-1)+fib(index-2);
    }
}

兔子问题

兔子问题：最初有1对兔子，三个月之后，每个月都会生产一对兔子(前提，兔子不会死)，那么第n个月之后一共有多少对兔子

package com.autumn;

/**
 * 生兔子
 * 有一对兔子，生长三个月后。开始生第一对兔子，并且以后每月生一对兔子，小兔子生长三个月后，也开始生兔子，问N个月后兔子的总数量
 * 月份对应的兔子数: 1,1,2,3,5,8
 * 可以看出兔子第三个月才能生一对,也就是说第三个月兔子数 = 第二个月现有兔子的总数 + 第一个月能生的兔子数(即将出生数=能生数)
 * 递归的方式：
 * （1）规律：每个月兔子的总数是前两个月兔子总数之和
 * （2）出口：前两个月都是一对
 */
public class Recursive {

    public static void main(String[] args) {
        for (int i= 1;i<30;i++){
            System.out.println(rabbit(i));
        }
    }

    /**
     * 当月兔子总数
     * @param index 月份,从1开始
     * @return 兔子的值
     */
    public static int rabbit(int index){
        /*如果月份是1,返回1*/
        if (index == 1){
            return 1;
        }
        /*如果月份是2,返回1*/
        if (index ==2){
            return 1;
        }
        //否则,返回前两项的和
        return rabbit(index-1)+ rabbit(index-2);
    }
}