递归在程序语言中简单的理解是：方法自己调用自己

想要用递归必须知道两个条件：

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

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

求数组最大的值

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

我们又可以运用1和整体的思想来找到规律

  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. 而我们要做的就是找出这个整体的最大值与2进行比较。找出整体的最大值又是和我们的初始目的(找出最大值)是一样的，也就可以写成if( 2>findMax() )return 2 else return findMax()

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

  1. /**
  2.      * @param arrays
  3.      * @param L 0
  4.      * @param R arrays.length-1
  5.      * @return
  6.      */
  7.     int findMax(int[] arrays,int L,int R){
  9.         if(L==R){
  10.             return arrays[L];
  11.         }else{
  12.             int first = arrays[L];
  13.             int restMax = findMax(arrays,L+1,R);
  15.             if(first>restMax){
  16.                 return first;
  17.             }else{
  18.                 return restMax;
  19.             }
  20.         }
  21.     }

冒泡排序的递归实现

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

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

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

  2. 递归出口：当只有一个元素时，即不用比较了：L==R

  1. /**
  2.      * @param arrays
  3.      * @param L 0
  4.      * @param R arrays.length-1
  5.      */
  6.     void bubbleSort(int[] arrays,int L,int R){
  8.         int temp;
  10.         if(L==R){
  11.             return;
  12.         }
  13.         else{
  14.             for(int i=L;i<R;i++){
  15.                 if(arrays[i]>arrays[i+1]){
  16.                     temp = arrays[i];
  17.                     arrays[i] = arrays[i+1];
  18.                     arrays[i+1] = temp;
  19.                 }
  20.             }
  21.         }
  23.         bubbleSort(arrays,L,R-1);
  24.     }

暂时举两个例子，后面继续补充