什么是递归？

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

递归和循环非常像，循环都可以写成递归。递归未必能写成循环。

有了循环，为什么还需要递归呢？

在某些情况下，使用递归会比循环简单很多很多。（斐波那契数列，汉诺塔）。

使用递归我们需要 注意什么？
我们需要记住，想要用递归必须知道两个条件：

  • 递归的出口（终止递归的条件）
  • 递归表达式（规律）

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

案例：

求和：
使用for遍历的方式进行求和（1到100的求和）

  1.     int sum = 0;
  2.     for (int i = 1; i <= 100; i++) {
  3.         sum = sum + i;
  4.     }

使用递归求和：（需要知道两个必要条件：递归出口，递归表达式）
递归出口：if(n=1) return 1;

  1.     public static void main(String[] args) {
  2.       sum(100);
  3.     }
  5.     /**
  6.      *
  7.      * @param n 要加到的数字，比如题目的100
  8.      * @return
  9.      */
  10.     public static int sum(int n) {
  12.         if (n == 1) {
  13.             return 1;
  14.         } else {
  15.             return sum(n - 1) + n;
  16.         }
  17.     }

案例二：数组内部的最大值

使用for循环：

  1.     int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 2};
  3.     //将数组的第一个假设是最大值
  4.     int max = arrays[0];
  6.     for (int i = 1; i < arrays.length; i++) {
  8.         if (arrays[i] > max) {
  9.             max = arrays[i];
  10.         }
  11.     }

使用递归：
递归出口：如果数组中只有一个元素就是他的出口了。

  1.   public static void main(String[] args) {
  3.         int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};
  5.      findMax(arrays, 0, arrays.length - 1);
  8.     }
  11.     /**
  12.      * 递归，找出数组最大的值
  13.      * @param arrays 数组
  14.      * @param L      左边界，第一个数
  15.      * @param R      右边界，数组的长度
  16.      * @return
  17.      */
  19.     public static int findMax(int[] arrays, int L, int R) {
  21.         //如果该数组只有一个数，那么最大的就是该数组第一个值了
  22.         if (L == R) {
  23.             return arrays[L];
  24.         } else {
  26.             int a = arrays[L];
  27.             int b = findMax(arrays, L + 1, R);//找出整体的最大值
  29.             if (a > b) {
  30.                 return a;
  31.             } else {
  32.                 return b;
  33.             }
  34.         }
  36.     }

案例：冒泡排序递归写法

  1.    public static void main(String[] args) {
  3.         int[] arrays = {2, 3, 4, 5, 1, 5, 2, 9, 5, 6, 8, 3, 1};
  4.         bubbleSort(arrays, 0, arrays.length - 1);
  5.         System.out.println(arrays);
  8.     }
  10.     public static void bubbleSort(int[] arrays, int L, int R) {
  12.         int temp;
  14.         //如果只有一个元素了，那什么都不用干
  15.         if (L == R) ;
  17.         else {
  18.             for (int i = L; i < R; i++) {
  19.                 if (arrays[i] > arrays[i + 1]) {
  20.                     temp = arrays[i];
  21.                     arrays[i] = arrays[i + 1];
  22.                     arrays[i + 1] = temp;
  23.                 }
  24.             }
  26.             //第一趟排序后已经将最大值放到数组最后面了
  28.             //接下来是排序"整体"的数据了
  29.             bubbleSort(arrays, L, R - 1);
  31.         }
  32.     }

案例：斐波那契数列（前两项之和等于第三项）
菲波那切数列长这个样子：{1 1 2 3 5 8 13 21 34 55….. n }
递归出口：if(n==1) retrun 1 if(n==2) return 2
递归表达式：Z = (n-2) + (n-1)

  1.     public static void main(String[] args) {
  3.         int[] arrays = {1, 1, 2, 3, 5, 8, 13, 21};
  4.         //bubbleSort(arrays, 0, arrays.length - 1);
  6.         int fibonacci = fibonacci(10);
  7.         System.out.println(fibonacci);
  10.     }
  12.     public static int fibonacci(int n) {
  13.         if (n == 1) {
  14.             return 1;
  15.         } else if (n == 2) {
  16.             return 1;
  17.         } else {
  18.             return (fibonacci(n - 1) + fibonacci(n - 2));
  19.         }
  21.     }