Java中的遞歸方法示例介紹

Posted on by

遞歸

方法定義本身調用方法本身的現象叫做遞歸

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

那什麼是遞歸呢？

舉例：

從前有座山，山裡有座廟，廟裡有個老和尚，老和尚在給小和尚說故事，說的故事內容是：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

從前有座山，山裡有座廟，廟裡有個老和尚，老和尚在給小和尚說故事，說的故事內容是：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

從前有座山，山裡有座廟，廟裡有個老和尚，老和尚在給小和尚說故事，說的故事內容是：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

從前有座山，山裡有座廟，廟裡有個老和尚，老和尚在給小和尚說故事，說的故事內容是：。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

。。。。。。。。。。。。。。。。。。。。。。廟不在瞭，遞歸結束。

舉例：

學習-高新就業-娶媳婦-生娃-學習-高薪就業-娶媳婦-生娃-學習-高新就業-娶媳婦-生娃-學習-高薪就業-娶媳婦-生娃-學習-高新就業-娶媳婦-生娃-學習-高薪就業-娶媳婦-生娃-學習-高新就業-娶媳婦-生娃-學習-高薪就業-娶媳婦-生娃-學習-高新就業-娶媳婦-生娃-學習-高薪就業-娶媳婦-生娃

娶不到媳婦，生不瞭娃，遞歸結束。

遞歸的註意事項：

遞歸一定要有一個出口，結束條件，否則就是死循環遞歸的次數不能太多，否則就會發生內存溢出構造方法不能使用遞歸

案例一

參考代碼：

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

輸出結果：

 10    9    8    7    6    5    4    3    2    1    0    結束循環

遞歸求階乘

5的階乘：

        遞歸求階乘：

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

               = 5*4!

               = 5*4*3!

               = 5*4*3*2!

               = 5*4*3*2*1!

不使用遞歸實現階乘

參考代碼：

/*
        遞歸求階乘：
            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);
    }
}

 輸出結果：

5的階乘是：120

使用遞歸實現階乘

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

    2、尋找規律：
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);
        }
    }
}

輸出結果：

120

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

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

 找規律：

     月         兔子對數

     1             1

     2             1

     3             2

     4             3

     5             5

     6             8

     7             13

     …

由此可見，兔子的對數數量是：

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

發現的規律是：

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

     2、說明每一項的前兩項的數據是已知的

 如何實現呢？

1、數組方式實現

2、基本變量實現

3、遞歸方式實現

使用數組實現

參考代碼：

public class RecursionDemo4 {
    public static void main(String[] args) {
        //使用數組實現
        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個月的兔子對數為：" + arr[19]);
    }
}

 輸出結果：

第20個月的兔子對數為：6765

使用遞歸實現

參考代碼：

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

輸出結果：

第20個月的兔子對數為：6765

總結

到此這篇關於Java中的遞歸方法示例介紹的文章就介紹到這瞭,更多相關Java遞歸方法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：