Java中的遞歸方法示例介紹

更新時間：2021年12月27日 08:57:29 作者：liangzai2048

大家好，本篇文章主要講的是Java中的遞歸方法示例介紹，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽

遞歸

方法定義本身調(diào)用方法本身的現(xiàn)象叫做遞歸

在這之前我們學的東西：例如StringBuffer.append().append().append()這個不叫遞歸。這個叫方法的連續(xù)調(diào)用Math.max(Math.max(a,b),c)也不是遞歸，那這些是什么呢？這些是方法的調(diào)用。

那什么是遞歸呢？

舉例：

從前有座山，山里有座廟，廟里有個老和尚，老和尚在給小和尚說故事，說的故事內(nèi)容是：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

從前有座山，山里有座廟，廟里有個老和尚，老和尚在給小和尚說故事，說的故事內(nèi)容是：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

從前有座山，山里有座廟，廟里有個老和尚，老和尚在給小和尚說故事，說的故事內(nèi)容是：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

從前有座山，山里有座廟，廟里有個老和尚，老和尚在給小和尚說故事，說的故事內(nèi)容是：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

。。。。。。。。。。。。。。。。。。。。。。廟不在了，遞歸結(jié)束。

舉例：

學習-高新就業(yè)-娶媳婦-生娃-學習-高薪就業(yè)-娶媳婦-生娃-學習-高新就業(yè)-娶媳婦-生娃-學習-高薪就業(yè)-娶媳婦-生娃-學習-高新就業(yè)-娶媳婦-生娃-學習-高薪就業(yè)-娶媳婦-生娃-學習-高新就業(yè)-娶媳婦-生娃-學習-高薪就業(yè)-娶媳婦-生娃-學習-高新就業(yè)-娶媳婦-生娃-學習-高薪就業(yè)-娶媳婦-生娃

娶不到媳婦，生不了娃，遞歸結(jié)束。

遞歸的注意事項：

遞歸一定要有一個出口，結(jié)束條件，否則就是死循環(huán)遞歸的次數(shù)不能太多，否則就會發(fā)生內(nèi)存溢出構(gòu)造方法不能使用遞歸

案例一

參考代碼：

public class RecursionDemo1 {
    public static void main(String[] args) {
        show(10);
    }
 
    private static void show(int i) {
        //定義結(jié)束條件
        if (i<0){
            System.out.println("結(jié)束循環(huán)");
        }else {
            System.out.print(i + "\t");
            show(--i);
        }
    }
 
}

輸出結(jié)果：

?10?? ?9?? ?8?? ?7?? ?6?? ?5?? ?4?? ?3?? ?2?? ?1?? ?0?? ?結(jié)束循環(huán)

遞歸求階乘

5的階乘：

? ? ? ? 遞歸求階乘：

? ? ? ? ? ? 5！= 5*4*3*2*1 = 120

? ? ? ? ? ? ? ?= 5*4!

? ? ? ? ? ? ? ?= 5*4*3!

? ? ? ? ? ? ? ?= 5*4*3*2!

? ? ? ? ? ? ? ?= 5*4*3*2*1!

不使用遞歸實現(xiàn)階乘

參考代碼：

/*
        遞歸求階乘：
            5！= 5*4*3*2*1 = 120
               = 5*4!
               = 5*4*3!
               = 5*4*3*2!
               = 5*4*3*2*1!
 */
public class RecursionDemo2 {
    public static void main(String[] args) {
        //不使用遞歸的做法
        int result = 1;
        for (int i = 2; i<=5; i++){
            result = result * i;
        }
        System.out.println("5的階乘是：" + result);
    }
}

?輸出結(jié)果：

5的階乘是：120

使用遞歸實現(xiàn)階乘

遞歸的實現(xiàn)思想：
1、結(jié)束條件：
if(i==1){return 1}

??? 2、尋找規(guī)律：
if(i!=1){
return i * recursionFun(i-1);
}

參考代碼：

/*
        遞歸求階乘：
            5！= 5*4*3*2*1 = 120
               = 5*4!
               = 5*4*3!
               = 5*4*3*2!
               = 5*4*3*2*1!
 */
public class RecursionDemo3 {
    public static void main(String[] args) {
 
        System.out.println(recursionFun(5));
 
    }
 
    private static int recursionFun(int i) {
 
        if (i==1){
            return 1;
        }else {
            //5 * recursionFun(4)
            //5 * 4 * recursionFun(3)
            //5 * 4 * 3 * recursionFun(2)
            //5 * 4 * 3 * 2 * recursionFun(1)
            //5 * 4 * 3 * 2 * 1
            return i * recursionFun(i-1);
        }
    }
}

輸出結(jié)果：

120

澳大利亞不死神兔（斐波那契數(shù)列）

有一對兔子，從出生第三個月開始，每個月都生一對兔子，小兔子長到三個月后每個月又生一對兔子，假設(shè)這些兔子都不會死，問：20個月，又多少對兔子？

?找規(guī)律：

? ? ?月? ? ? ? ?兔子對數(shù)

? ? ?1? ? ? ? ? ? ?1

? ? ?2? ? ? ? ? ? ?1

? ? ?3? ? ? ? ? ? ?2

? ? ?4? ? ? ? ? ? ?3

? ? ?5? ? ? ? ? ? ?5

? ? ?6? ? ? ? ? ? ?8

? ? ?7? ? ? ? ? ? ?13

? ? ?...

由此可見，兔子的對數(shù)數(shù)量是：

1、1、2、3、5、8、13、21...

發(fā)現(xiàn)的規(guī)律是：

? ? ?1、從第三項開始，每一項都是前兩項之和

? ? ?2、說明每一項的前兩項的數(shù)據(jù)是已知的

?如何實現(xiàn)呢？

1、數(shù)組方式實現(xiàn)

2、基本變量實現(xiàn)

3、遞歸方式實現(xiàn)

使用數(shù)組實現(xiàn)

參考代碼：

public class RecursionDemo4 {
    public static void main(String[] args) {
        //使用數(shù)組實現(xiàn)
        int[] arr = new int[20];
        arr[0] = 1;
        arr[1] = 1;
 
        for (int i =2 ;i < arr.length;i++){
            arr[i] = arr[i-2] + arr[i -1];
        }
        System.out.println("第20個月的兔子對數(shù)為：" + arr[19]);
    }
}

?輸出結(jié)果：

第20個月的兔子對數(shù)為：6765

使用遞歸實現(xiàn)

參考代碼：

public class RecursionDemo5 {
    public static void main(String[] args) {
 
        System.out.println("第20個月的兔子對數(shù)為：" + ribbateFibonacci(20));
 
    }
 
    private static int ribbateFibonacci(int month) {
 
        if (month == 1 || month ==2 ){
            return 1;
        }else {
            return ribbateFibonacci(month-1) +  ribbateFibonacci(month-2);
        }
    }
}

輸出結(jié)果：