递归就这么简单

而我们要做的就是找出这个整体的最大值与2进行比较。找出整体的最大值又是和我们的初始目的(找出最大值)是一样的

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

递归出口，如果数组只有1个元素时，那么这个数组最大值就是它了。

使用到数组的时候，我们通常为数组设定左边界和右边界，这样比较好地进行切割

L表示左边界，往往表示的是数组第一个元素，也就会赋值为0(角标为0是数组的第一个元素)

R表示右边界，往往表示的是数组的长度，也就会赋值为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));


    }
  

    /**
     * 递归，找出数组最大的值
     * @param arrays 数组
     * @param L      左边界，第一个数
     * @param R      右边界，数组的长度
     * @return
     */

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

        //如果该数组只有一个数，那么最大的就是该数组第一个值了
        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;
            }
        }

    }

在冒泡排序章节中给出了C语言的递归实现冒泡排序，那么现在我们已经使用递归的基本思路了，我们使用Java来重写一下看看：

冒泡排序：俩俩交换，在第一趟排序中能够将最大值排到最后面，外层循环控制排序趟数，内层循环控制比较次数

以递归的思想来进行改造：

当第一趟排序后，我们可以将数组最后一位(R)和数组前面的数(L,R-1)进行切割，数组前面的数(L,R-1)看成是一个整体，这个整体又是和我们的初始目的(找出最大值，与当前趟数的末尾处交换)是一样的

递归出口：当只有一个元素时，即不用比较了：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;
                }
            }

            //第一趟排序后已经将最大值放到数组最后面了

            //接下来是排序"整体"的数据了
            bubbleSort(arrays, L, R - 1);

        }
    }

接触过C语言的同学很可能就知道什么是费波纳切数列了，因为往往做练习题的时候它就会出现，它也是递归的典型应用。

菲波那切数列长这个样子：{1 1 2 3 5 8 13 21 34 55..... n }

数学好的同学可能很容易就找到规律了：前两项之和等于第三项

例如：

     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));
        }

    }

图片来源百度百科：

玩汉诺塔的规则很简单：

有三根柱子，原始装满大小不一的盘子的柱子我们称为A，还有两根空的柱子，我们分别称为B和C(任选)

最终的目的就是将A柱子的盘子全部移到C柱子中

移动的时候有个规则：一次只能移动一个盘子，小的盘子不能在大的盘子上面(反过来：大的盘子不能在小的盘子上面)

我们下面就来玩一下：

只有一个盘子：

将A柱子的盘子直接移动到C柱子中

完成游戏

只有两个盘子：

将A柱子上的小盘子移动到B柱子中

将A柱子上的大盘子移动到C柱子中

最后将在B柱子的小盘子移动到C柱子大盘子中

完成游戏

只有三个盘子：

将A柱子小的盘子移动到C柱子中

将A柱子上的中盘子移动到B柱子中

将C柱子小盘子移动到B柱子中盘子中

将A柱子的大盘子移动到C柱子中

将B柱子的小盘子移动到A柱子中

将B柱子的中盘子移动到C柱子中

最后将A柱子的小盘子移动到C柱子中

完成游戏

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

从前三次玩法中我们就可以发现的规律：

想要将最大的盘子移动到C柱子，就必须将其余的盘子移到B柱子处(借助B柱子将最大盘子移动到C柱子中[除了最大盘子，将所有盘子移动到B柱子中])[递归表达式]

当C柱子有了最大盘子时，所有的盘子在B柱子。现在的目的就是借助A柱子将B柱子的盘子都放到C柱子中(和上面是一样的，已经发生递归了)

当只有一个盘子时，就可以直接移动到C柱子了(递归出口)

A柱子称之为起始柱子，B柱子称之为中转柱子，C柱子称之为目标柱子

从上面的描述我们可以发现，起始柱子、中转柱子它们的角色是会变的（A柱子开始是起始柱子，第二轮后就变成了中转柱子了。B柱子开始是目标柱子，第二轮后就变成了起始柱子。总之，起始柱子、中转柱子的角色是不停切换的)

简单来说就分成三步：

把 n-1 号盘子移动到中转柱子

把最大盘子从起点移到目标柱子

把中转柱子的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 中转柱子
     * @param target 目标柱子
     */
    public static void hanoi(int n, char start, char transfer, char target) {


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

            //起始柱子借助目标柱子将盘子都移动到中转柱子中(除了最大的盘子)
            hanoi(n - 1, start, target, transfer);
            System.out.println(start + "---->" + target);

            //中转柱子借助起始柱子将盘子都移动到目标柱子中
            hanoi(n - 1, transfer, start, target);

        }
    }

我们来测试一下看写得对不对：

参考资料：

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

递归的确是一个比较难理解的东西，好几次都把我绕进去了....

要使用递归首先要知道两件事：

递归出口(终止递归的条件)

递归表达式(规律)

在递归中常常用”整体“的思想，在汉诺塔例子中也不例外：将最大盘的盘子看成1，上面的盘子看成一个整体。那么我们在演算的时候就很清晰了：将”整体“搬到B柱子，将最大的盘子搬到C柱子，最后将B柱子的盘子搬到C柱子中

因为我们人脑无法演算那么多的步骤，递归是用计算机来干的，只要我们找到了递归表达式和递归出口就要相信计算机能帮我们搞掂。

在编程语言中，递归的本质是方法自己调用自己，只是参数不一样罢了。

最后，我们来看一下如果是5个盘子，要运多少次才能运完：

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

如果文章有错的地方欢迎指正，大家互相交流。习惯在微信看技术文章，想要获取更多的Java资源的同学，可以关注微信公众号:Java3y