Java中的递归以及不死神兔实例（斐波那契数列）

浅浅的花香味﹌ 2022-04-17 00:47 160阅读 0赞

**递归**  
1、递归次数不要太多，太占内存  
2、递归一定要有出口  
3、构造方法不能递归使用  
**三种方法实现实例：**

package test17_digui;
    
    import java.util.Scanner;
    
    /*
     * 题目：有一对兔子，从出生后第3个月起每个月都生1对兔子，小兔子第三个月后也可以生一对兔子，
     * 		假如兔子不死，在指定月份时刻一共可以有多少对兔子
     * 
     * 分析：
     * 		第一个月：1
     * 		第二个月：1
     * 		第三个月：2
     * 		第四个月：3
     * 		第五个月：5
     * 		第六个月：8
     * 		。。。。。
     * 		
     * 		其实指定月份兔子的总数为此月之前两个月兔子总数之和。
     * 
     * 实现3种方法
     * 		1、数组实现
     * 		2、相邻变量实现
     * 		3、递归实现
     */
    public class DiGuiDemo {
        
    	public static void main(String[] args) {
        
    		Scanner sc=new Scanner(System.in);
    		System.out.println("请输入当前月份");
    		int m=sc.nextInt();
    		int n1=0;
    		int n2=0;
    		int n3=0;
    		sc.close();
    		
    		//数组实现
    		if(m<=2) {
        
    			n1=1;
    			
    		}else {
        
    			int []x=new int[m];
    			x[0]=1;
    			x[1]=1;
    			for(int i=2;i<m;i++ ) {
        
    				x[i]=x[i-1]+x[i-2];		
    			}	
    			n1=x[m-1];
    		}
    		System.out.println("方法一：数组实现");
    		System.out.println("\t"+"第"+m+"月份共有"+n1+"对兔子");
    		System.out.println("--------------------------");
    		
    		
    		//相邻变量实现
    		if(m<=2) {
        
    			n2=1;
    			
    		}else {
        
    			int a=1;
    			int b=1;
    			int temp=0;
    			for(int i=0;i<m-2;i++) {
        
    				temp=a;
    				a=b;
    				b=temp+b;
    			}
    			n2=b;
    		}
    		System.out.println("方法二：相邻变量实现");
    		System.out.println("\t"+"第"+m+"月份共有"+n2+"对兔子");
    		System.out.println("--------------------------");
    		
    		//递归实现
    		n3=digui(m);
    		System.out.println("方法三：递归实现");
    		System.out.println("\t"+"第"+m+"月份共有"+n3+"对兔子");
    	}
    
    	private static int digui(int m) {
        
    		// TODO Auto-generated method stub
    		if(m<=2) {
        
    			return 1;
    		}else {
        
    			return digui(m-1)+digui(m-2);
    		}
    		
    	}
    
    }

**输出结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pmbGl1OTY_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pmbGl1OTY_size_16_color_FFFFFF_t_70]: /images/20220417/e32f9853a6b5434882dcc94b6b220fd8.png