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

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

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

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

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

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

那么可以看看我們遞歸的寫(xiě)法了：

  public static void main(String[] args) {

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

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


    }
  

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

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

        //如果該數(shù)組只有一個(gè)數(shù)，那么最大的就是該數(shù)組第一個(gè)值了
        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語(yǔ)言的遞歸實(shí)現(xiàn)冒泡排序，那么現(xiàn)在我們已經(jīng)使用遞歸的基本思路了，我們使用Java來(lái)重寫(xiě)一下看看：

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

以遞歸的思想來(lái)進(jìn)行改造：

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

遞歸出口：當(dāng)只有一個(gè)元素時(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("公眾號(hào)：Java3y：" + arrays);


    }

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

        int temp;

        //如果只有一個(gè)元素了，那什么都不用干
        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ù)組最后面了

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

        }
    }

接觸過(guò)C語(yǔ)言的同學(xué)很可能就知道什么是費(fèi)波納切數(shù)列了，因?yàn)橥鼍毩?xí)題的時(shí)候它就會(huì)出現(xiàn)，它也是遞歸的典型應(yīng)用。

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

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

例如：

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

如果讓我們求出第n項(xiàng)是多少，那么我們就可以很簡(jiǎn)單寫(xiě)出對(duì)應(yīng)的遞歸表達(dá)式了：Z = (n-2) + (n-1)

遞歸出口在本題目是需要有兩個(gè)的，因?yàn)?strong>它是前兩項(xiàng)加起來(lái)才得出第三項(xiàng)的值

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

下面就來(lái)看一下完整的代碼吧：

    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("公眾號(hào)：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));
        }

    }

圖片來(lái)源百度百科：

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

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

最終的目的就是將A柱子的盤(pán)子全部移到C柱子中

移動(dòng)的時(shí)候有個(gè)規(guī)則：一次只能移動(dòng)一個(gè)盤(pán)子，小的盤(pán)子不能在大的盤(pán)子上面(反過(guò)來(lái)：大的盤(pán)子不能在小的盤(pán)子上面)

我們下面就來(lái)玩一下：

只有一個(gè)盤(pán)子：

將A柱子的盤(pán)子直接移動(dòng)到C柱子中

完成游戲

只有兩個(gè)盤(pán)子：

將A柱子上的小盤(pán)子移動(dòng)到B柱子中

將A柱子上的大盤(pán)子移動(dòng)到C柱子中

最后將在B柱子的小盤(pán)子移動(dòng)到C柱子大盤(pán)子中

完成游戲

只有三個(gè)盤(pán)子：

將A柱子小的盤(pán)子移動(dòng)到C柱子中

將A柱子上的中盤(pán)子移動(dòng)到B柱子中

將C柱子小盤(pán)子移動(dòng)到B柱子中盤(pán)子中

將A柱子的大盤(pán)子移動(dòng)到C柱子中

將B柱子的小盤(pán)子移動(dòng)到A柱子中

將B柱子的中盤(pán)子移動(dòng)到C柱子中

最后將A柱子的小盤(pán)子移動(dòng)到C柱子中

完成游戲

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

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

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

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

當(dāng)只有一個(gè)盤(pán)子時(shí)，就可以直接移動(dòng)到C柱子了(遞歸出口)

A柱子稱(chēng)之為起始柱子，B柱子稱(chēng)之為中轉(zhuǎn)柱子，C柱子稱(chēng)之為目標(biāo)柱子

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

簡(jiǎn)單來(lái)說(shuō)就分成三步：

把 n-1 號(hào)盤(pán)子移動(dòng)到中轉(zhuǎn)柱子

把最大盤(pán)子從起點(diǎn)移到目標(biāo)柱子

把中轉(zhuǎn)柱子的n-1號(hào)盤(pán)子也移到目標(biāo)柱子

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

    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("公眾號(hào)：Java3y" );


    }

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


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

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

            //中轉(zhuǎn)柱子借助起始柱子將盤(pán)子都移動(dòng)到目標(biāo)柱子中
            hanoi(n - 1, transfer, start, target);

        }
    }

我們來(lái)測(cè)試一下看寫(xiě)得對(duì)不對(duì)：

參考資料：

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

遞歸的確是一個(gè)比較難理解的東西，好幾次都把我繞進(jìn)去了....

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

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

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

在遞歸中常常用”整體“的思想，在漢諾塔例子中也不例外：將最大盤(pán)的盤(pán)子看成1，上面的盤(pán)子看成一個(gè)整體。那么我們?cè)谘菟愕臅r(shí)候就很清晰了：將”整體“搬到B柱子，將最大的盤(pán)子搬到C柱子，最后將B柱子的盤(pán)子搬到C柱子中

因?yàn)槲覀內(nèi)四X無(wú)法演算那么多的步驟，遞歸是用計(jì)算機(jī)來(lái)干的，只要我們找到了遞歸表達(dá)式和遞歸出口就要相信計(jì)算機(jī)能幫我們搞掂。

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

最后，我們來(lái)看一下如果是5個(gè)盤(pán)子，要運(yùn)多少次才能運(yùn)完：

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

如果文章有錯(cuò)的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號(hào):Java3y