递归介绍
本来预算此章节是继续写快速排序的，然而编写快速排序往往是递归来写的，并且递归可能不是那么好理解，于是就有了这篇文章。
在上面提到了递归这么一个词，递归在程序语言中简单的理解是：方法自己调用自己
递归其实和循环是非常像的，循环都可以改写成递归，递归未必能改写成循环，这是一个充分不必要的条件。
- 那么，有了循环，为什么还要用递归呢？？在某些情况下(费波纳切数列，汉诺塔)，使用递归会比循环简单很多很多
- 话说多了也无益，让我们来感受一下递归吧。
我们初学编程的时候肯定会做过类似的练习：
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); } }
