而我們要做的就是找出這個整體的最大值與2進行比較。找出整體的最大值又是和我們的初始目的(找出最大值)是一樣的

也就可以寫成if( 2>findMax() )return 2 else return findMax()

遞歸出口，如果數(shù)組只有1個元素時，那么這個數(shù)組最大值就是它了。

使用到數(shù)組的時候，我們通常為數(shù)組設定左邊界和右邊界，這樣比較好地進行切割

L表示左邊界，往往表示的是數(shù)組第一個元素，也就會賦值為0(角標為0是數(shù)組的第一個元素)

R表示右邊界，往往表示的是數(shù)組的長度，也就會賦值為arrays.length-1（長度-1在角標中才是代表最后一個元素)

那么可以看看我們遞歸的寫法了：

  public static void main(String[] args) {

        int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};

        System.out.println("公眾號：Java3y：" + findMax(arrays, 0, arrays.length - 1));


    }
  

    /**
     * 遞歸，找出數(shù)組最大的值
     * @param arrays 數(shù)組
     * @param L      左邊界，第一個數(shù)
     * @param R      右邊界，數(shù)組的長度
     * @return
     */

    public static int findMax(int[] arrays, int L, int R) {

        //如果該數(shù)組只有一個數(shù)，那么最大的就是該數(shù)組第一個值了
        if (L == R) {
            return arrays[L];
        } else {

            int a = arrays[L];
            int b = findMax(arrays, L + 1, R);//找出整體的最大值

            if (a > b) {
                return a;
            } else {
                return b;
            }
        }

    }

在冒泡排序章節(jié)中給出了C語言的遞歸實現(xiàn)冒泡排序，那么現(xiàn)在我們已經(jīng)使用遞歸的基本思路了，我們使用Java來重寫一下看看：

冒泡排序：倆倆交換，在第一趟排序中能夠?qū)⒆畲笾蹬诺阶詈竺?，外層循環(huán)控制排序趟數(shù)，內(nèi)層循環(huán)控制比較次數(shù)

以遞歸的思想來進行改造：

當?shù)谝惶伺判蚝?，我們可以將?shù)組最后一位(R)和數(shù)組前面的數(shù)(L,R-1)進行切割，數(shù)組前面的數(shù)(L,R-1)看成是一個整體，這個整體又是和我們的初始目的(找出最大值，與當前趟數(shù)的末尾處交換)是一樣的

遞歸出口：當只有一個元素時，即不用比較了：L==R

    public static void main(String[] args) {

        int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};
        bubbleSort(arrays, 0, arrays.length - 1);
        System.out.println("公眾號：Java3y：" + arrays);


    }

    public static void bubbleSort(int[] arrays, int L, int R) {

        int temp;

        //如果只有一個元素了，那什么都不用干
        if (L == R) ;

        else {
            for (int i = L; i < R; i++) {
                if (arrays[i] > arrays[i + 1]) {
                    temp = arrays[i];
                    arrays[i] = arrays[i + 1];
                    arrays[i + 1] = temp;
                }
            }

            //第一趟排序后已經(jīng)將最大值放到數(shù)組最后面了

            //接下來是排序"整體"的數(shù)據(jù)了
            bubbleSort(arrays, L, R - 1);

        }
    }

接觸過C語言的同學很可能就知道什么是費波納切數(shù)列了，因為往往做練習題的時候它就會出現(xiàn)，它也是遞歸的典型應用。

菲波那切數(shù)列長這個樣子：{1 1 2 3 5 8 13 21 34 55..... n }

數(shù)學好的同學可能很容易就找到規(guī)律了：前兩項之和等于第三項

例如：

     1 + 1 = 2
    2 + 3 = 5
    13 + 21 = 34

如果讓我們求出第n項是多少，那么我們就可以很簡單寫出對應的遞歸表達式了：Z = (n-2) + (n-1)

遞歸出口在本題目是需要有兩個的，因為它是前兩項加起來才得出第三項的值

同樣地，那么我們的遞歸出口可以寫成這樣：if(n==1) retrun 1 if(n==2) return 2

下面就來看一下完整的代碼吧：

    public static void main(String[] args) {

        int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
        //bubbleSort(arrays, 0, arrays.length - 1);

        int fibonacci = fibonacci(10);
        System.out.println("公眾號：Java3y：" + fibonacci);


    }

    public static int fibonacci(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 1;
        } else {
            return (fibonacci(n - 1) + fibonacci(n - 2));
        }

    }

圖片來源百度百科：

玩漢諾塔的規(guī)則很簡單：

有三根柱子，原始裝滿大小不一的盤子的柱子我們稱為A，還有兩根空的柱子，我們分別稱為B和C(任選)

最終的目的就是將A柱子的盤子全部移到C柱子中

移動的時候有個規(guī)則：一次只能移動一個盤子，小的盤子不能在大的盤子上面(反過來：大的盤子不能在小的盤子上面)

我們下面就來玩一下：

只有一個盤子：

將A柱子的盤子直接移動到C柱子中

完成游戲

只有兩個盤子：

將A柱子上的小盤子移動到B柱子中

將A柱子上的大盤子移動到C柱子中

最后將在B柱子的小盤子移動到C柱子大盤子中

完成游戲

只有三個盤子：

將A柱子小的盤子移動到C柱子中

將A柱子上的中盤子移動到B柱子中

將C柱子小盤子移動到B柱子中盤子中

將A柱子的大盤子移動到C柱子中

將B柱子的小盤子移動到A柱子中

將B柱子的中盤子移動到C柱子中

最后將A柱子的小盤子移動到C柱子中

完成游戲

.......................

從前三次玩法中我們就可以發(fā)現(xiàn)的規(guī)律：

想要將最大的盤子移動到C柱子，就必須將其余的盤子移到B柱子處(借助B柱子將最大盤子移動到C柱子中[除了最大盤子，將所有盤子移動到B柱子中])[遞歸表達式]

當C柱子有了最大盤子時，所有的盤子在B柱子?，F(xiàn)在的目的就是借助A柱子將B柱子的盤子都放到C柱子中(和上面是一樣的，已經(jīng)發(fā)生遞歸了)

當只有一個盤子時，就可以直接移動到C柱子了(遞歸出口)

A柱子稱之為起始柱子，B柱子稱之為中轉(zhuǎn)柱子，C柱子稱之為目標柱子

從上面的描述我們可以發(fā)現(xiàn)，起始柱子、中轉(zhuǎn)柱子它們的角色是會變的（A柱子開始是起始柱子，第二輪后就變成了中轉(zhuǎn)柱子了。B柱子開始是目標柱子，第二輪后就變成了起始柱子?？傊?strong>起始柱子、中轉(zhuǎn)柱子的角色是不停切換的)

簡單來說就分成三步：

把 n-1 號盤子移動到中轉(zhuǎn)柱子

把最大盤子從起點移到目標柱子

把中轉(zhuǎn)柱子的n-1號盤子也移到目標柱子

那么就可以寫代碼測試一下了(回看上面玩的過程)：

    public static void main(String[] args) {

        int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
        //bubbleSort(arrays, 0, arrays.length - 1);

        //int fibonacci = fibonacci(10);

        hanoi(3, "A", "B", "C");

        System.out.println("公眾號：Java3y" );


    }

    /**
     * 漢諾塔
     * @param n n個盤子
     * @param start 起始柱子
     * @param transfer 中轉(zhuǎn)柱子
     * @param target 目標柱子
     */
    public static void hanoi(int n, char start, char transfer, char target) {


        //只有一個盤子，直接搬到目標柱子
        if (n == 1) {
            System.out.println(start + "---->" + target);
        } else {

            //起始柱子借助目標柱子將盤子都移動到中轉(zhuǎn)柱子中(除了最大的盤子)
            hanoi(n - 1, start, target, transfer);
            System.out.println(start + "---->" + target);

            //中轉(zhuǎn)柱子借助起始柱子將盤子都移動到目標柱子中
            hanoi(n - 1, transfer, start, target);

        }
    }

我們來測試一下看寫得對不對：

參考資料：

https://www.zhihu.com/question/24385418

遞歸的確是一個比較難理解的東西，好幾次都把我繞進去了....

要使用遞歸首先要知道兩件事：

遞歸出口(終止遞歸的條件)

遞歸表達式(規(guī)律)

在遞歸中常常用”整體“的思想，在漢諾塔例子中也不例外：將最大盤的盤子看成1，上面的盤子看成一個整體。那么我們在演算的時候就很清晰了：將”整體“搬到B柱子，將最大的盤子搬到C柱子，最后將B柱子的盤子搬到C柱子中

因為我們?nèi)四X無法演算那么多的步驟，遞歸是用計算機來干的，只要我們找到了遞歸表達式和遞歸出口就要相信計算機能幫我們搞掂。

在編程語言中，遞歸的本質(zhì)是方法自己調(diào)用自己，只是參數(shù)不一樣罷了。

最后，我們來看一下如果是5個盤子，要運多少次才能運完：

PS:如果有更好的理解方法，或者我理解錯的地方大家可以在評論下留言一起交流哦！

如果文章有錯的地方歡迎指正，大家互相交流。習慣在微信看技術文章，想要獲取更多的Java資源的同學，可以關注微信公眾號:Java3y