递归就这么简单

不念不忘少年蓝@ 2021-09-15 01:18 293阅读 0赞

# 递归介绍 #

本来预算此章节是继续写快速排序的，然而编写快速排序往往是递归来写的，并且递归可能不是那么好理解，于是就有了这篇文章。

在上面提到了**递归**这么一个词，递归在程序语言中简单的理解是：**方法自己调用自己**

递归其实和循环是非常像的，循环**都**可以改写成递归，递归**未必**能改写成循环，这是一个充分不必要的条件。

*  那么，有了循环，为什么还要用递归呢？？**在某些情况下(费波纳切数列，汉诺塔)，使用递归会比循环简单很多很多**
 *  话说多了也无益，让我们来感受一下递归吧。

我们初学编程的时候肯定会做过类似的练习：

*  `1+2+3+4+....+100(n)`求和
 *  给出一个数组，求该数组内部的最大值

我们要记住的是，想要用递归必须知道两个条件：

*  **递归出口(终止递归的条件)**
 *  **递归表达式(规律)**

技巧：在递归中常常是将问题**切割成两个部分(1和整体的思想)**，这能够让我们快速找到递归表达式(规律)

## 一、求和 ##

如果我们使用`for`循环来进行求和`1+2+3+4+....+100`，那是很简单的：

int sum = 0;
        for (int i = 1; i <= 100; i++) {
    
            sum = sum + i;
    
        }
        System.out.println("公众号：Java3y：" + sum);

前面我说了，for循环都可以使用递归来进行改写，而使用递归必须要知道两个条件：1、递归出口，2、递归表达式(规律)

首先，我们来找出它的规律：`1+2+3+...+n`，这是一个求和的运算，那么我们可以假设`X=1+2+3+...+n`，可以将`1+2+3+...+(n-1)`看成是一个**整体**。而这个整体做的事又和我们的**初始目的(求和)**相同。以我们的高中数学知识我们又可以将上面的式子看成`X=sum(n-1)+n`

好了，我们找到我们的递归表达式(规律)，它就是`sum(n-1)+n`,那递归出口呢，这个题目的递归出口就有很多了，我列举一下：

*  如果`n=1`时，那么就返回`1`
 *  如果`n=2`时，那么就返回`3`(1+2)
 *  如果`n=3`时，那么就返回`6`(1+2+3)

当然了，我肯定是使用一个最简单的递归出口了：`if(n=1) return 1`

递归表达式和递归出口我们都找到了，下面就代码演示：

**递归出口为1：**

public static void main(String[] args) {
            System.out.println("公众号：Java3y：" + sum(100));
        }
    
        /** * * @param n 要加到的数字，比如题目的100 * @return */
        public static int sum(int n) {
    
            if (n == 1) {
                return 1;
            } else {
                return sum(n - 1) + n;
            }
        }

**递归出口为4：**

public static void main(String[] args) {
            System.out.println("公众号：Java3y：" + sum(100));
        }
    
        /** * * @param n 要加到的数字，比如题目的100 * @return */
        public static int sum(int n) {
    
            //如果递归出口为4，(1+2+3+4)
            if (n == 4) {
                return 10;
            } else {
                return sum(n - 1) + n;
            }
        }

结果都是一样的。

## 二、数组内部的最大值 ##

如果使用的是循环，那么我们通常这样实现：

int[] arrays = {
       2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2};
    
        //将数组的第一个假设是最大值
        int max = arrays[0];
    
        for (int i = 1; i < arrays.length; i++) {
    
            if (arrays[i] > max) {
                max = arrays[i];
            }
        }
    
        System.out.println("公众号：Java3y：" + max);

那如果我们用递归的话，那怎么用弄呢？首先还是先要找到**递归表达式(规律)和递归出口**

*  我们又可以运用1和整体的思想来找到规律  
    
    
     *  将数组第一个数->`2`与数组后面的数->`{3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}`进行**切割**，将数组后面的数看成是一个**整体**`X={3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2}`，那么我们就可以看成是**第一个数和一个整体进行比较**`if(2>X) return 2 else(2<X) return X`
     *  而我们要做的就是找出这个**整体**的最大值与`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);
    
            }
        }

![1624288e74695bf8_w_1025_h_579_f_png_s_36730][]

## 四、斐波那契数列 ##

接触过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));
            }
    
        }

## 五、汉诺塔算法 ##

图片来源百度百科：

![1624288e748ccaa9_w_600_h_600_f_jpeg_s_40444][]

玩汉诺塔的规则很简单：

*  有三根柱子，原始装满大小不一的盘子的柱子我们称为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柱子中
     *  完成游戏

![1624288e74e8c788_w_748_h_355_f_gif_s_197184][]  
…………………..

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

*  想要将最大的盘子移动到C柱子，就必须将**其余的盘子移到B柱子处(借助B柱子将最大盘子移动到C柱子中\[除了最大盘子，将所有盘子移动到B柱子中\])**\[递归表达式\]
 *  当C柱子有了最大盘子时，所有的盘子在B柱子。现在的目的就是**借助A柱子将B柱子的盘子都放到C柱子中(和上面是一样的，已经发生递归了)**
 *  **当只有一个盘子时，就可以直接移动到C柱子了(递归出口)**  
    
    
     *  **A柱子称之为起始柱子，B柱子称之为中转柱子，C柱子称之为目标柱子**
     *  从上面的描述我们可以发现，起始柱子、中转柱子它们的角色是会变的（A柱子开始是起始柱子，第二轮后就变成了中转柱子了。B柱子开始是目标柱子，第二轮后就变成了起始柱子。总之，**起始柱子、中转柱子的角色是不停切换的**)

简单来说就分成三步：

1.  把 n-1 号盘子移动到中转柱子
2.  把最大盘子从起点移到目标柱子
3.  把中转柱子的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);
    
            }
        }

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

![1624288e74e25ad4_w_1011_h_289_f_png_s_7263][]

参考资料：

*  [https://www.zhihu.com/question/24385418][https_www.zhihu.com_question_24385418]

## 六、总结 ##

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

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

*  递归出口(终止递归的条件)
 *  递归表达式(规律)

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

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

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

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

![1624288e74b4c7f6_w_763_h_663_f_png_s_11049][]

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

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

[1624288e74695bf8_w_1025_h_579_f_png_s_36730]: https://user-gold-cdn.xitu.io/2018/3/20/1624288e74695bf8?w=1025&h=579&f=png&s=36730
[1624288e748ccaa9_w_600_h_600_f_jpeg_s_40444]: https://user-gold-cdn.xitu.io/2018/3/20/1624288e748ccaa9?w=600&h=600&f=jpeg&s=40444
[1624288e74e8c788_w_748_h_355_f_gif_s_197184]: https://user-gold-cdn.xitu.io/2018/3/20/1624288e74e8c788?w=748&h=355&f=gif&s=197184
[1624288e74e25ad4_w_1011_h_289_f_png_s_7263]: https://user-gold-cdn.xitu.io/2018/3/20/1624288e74e25ad4?w=1011&h=289&f=png&s=7263
[https_www.zhihu.com_question_24385418]: https://www.zhihu.com/question/24385418
[1624288e74b4c7f6_w_763_h_663_f_png_s_11049]: https://user-gold-cdn.xitu.io/2018/3/20/1624288e74b4c7f6?w=763&h=663&f=png&s=11049