递归在编程世界的表现就是函数自己调用自己，只不过可能传入的参数在变。
递归的本质是栈：

微信公众号：小夕学算法

阶乘计算

  1. n! = 1 * 2 * 3 * 4 * …… * (n-1) * n

循环实现

  1. public static int factorial(int n) {
  2.     int factorial = 1;
  3.     for (int i = 1; i <= n; i++) {
  4.         factorial *= i;
  5.     }
  6.     return factorial;
  7. }

递归实现

数学表达式

  1. f(1) = 1
  2. f(n) = f(n-1) * n

代码实现

  1. public static int factorial(int n) {
  2.     //#1. 当 n = 1 时，递归结束
  3.     if (n == 1) {
  4.         return 1;
  5.     }
  6.     //#2. 把 factorial(n - 1) 的结果和 n 相乘，剩下的交给 factorial(n - 1) 来解决。
  7.     return n * factorial(n - 1);
  8. }

汉诺塔问题

汉诺塔是一个发源于印度的益智游戏，也叫河内塔。相传它源于印度神话中的大梵天创造的三个金刚柱，一根柱子上叠着上下从小到大64个黄金圆盘。大梵天命令婆罗门将这些圆盘按从小到大的顺序移动到另一根柱子上，其中大圆盘不能放在小圆盘上面。当这64个圆盘移动完的时候，世界就将毁灭。

递归 - 图1
汉诺塔问题源于印度神话
那么好多人会问64个圆盘移动到底会花多少时间？那么古代印度距离现在已经很远，这64个圆盘还没移动完么？我们来通过计算来看看要完成这个任务到底要多少时间？
我们首先利用数学上的数列知识来看看F(n=1)=1,F(n=2)=3,F(n=3)=7,F(n=4)=15……F(n)=2F(n-1)+1;
我们使用数学归纳法可以得出通项式：F(n)=2^n-1。当n为64时F(n=64)=18446744073709551615。
我们假设移动一次圆盘为一秒，那么一年为31536000秒。那么18446744073709551615/31536000约等于584942417355天，换算成年为5845.54亿年。
目前太阳寿命约为50亿年，太阳的完整寿命大约100亿年。所以我们整个人类文明都等不到移动完整圆盘的那一
天。
两个盘子：2^2-1=3次
递归 - 图2
三个盘子：2^3-1 = 7次
递归 - 图3
递归思想：
image.png
递归 - 图5

  3. function tower(n, form, use, to) {
  4.     if (n == 1) {
  5.         move(form, to);
  6.         return;
  7.     }
  8.     tower(n - 1, form, to, use);
  9.     tower(1, form, use, to);
  10.     tower(n - 1, use, form, to)
  12. }
  14. function move(from, to) {
  15.     console.log(`${from}————>${to}`);
  16. }
  19. tower(3, "A", "B", "C");

递归如何实现

基准条件

也就是递归的结束条件，没有结束条件，就会出现死循环。

递归公式

递归公式总是描述自己和下一个递归函数直接的递进关系。

总结

image.png

斐波那契数列

0，1，1，2，3，5，8，13，21，34，55，89，144……
第三个数字开始每个数等于前面两个数之和。
基准条件：第 0,1 个元素是 0 和 1.
递归公式：
递归 - 图7

  1. public class Recursive {
  3.   public static int fibonacci(int n) {
  4.     if (n == 0 || n == 1) {
  5.       return n;
  6.     }
  7.     return fibonacci(n - 1) + fibonacci(n - 2);
  8.   }
  10.   public static void main(String[] args) {
  11.     System.out.println("fibonacci(1) = " + fibonacci(1));
  12.     System.out.println("fibonacci(3) = " + fibonacci(3));
  13.     System.out.println("fibonacci(10) = " + fibonacci(10));
  14.   }
  15. }

递归实现二分插入排序

while的结束条件为基准条件
递归 - 图8

  2. import java.util.Arrays;
  4. public class Recursive {
  6.   // 查找应该插入的索引位置
  7.   public static int searchIndex(int[] array, int left, int right, int aim) {
  9.      // 基准条件，和之前 while 里面的条件刚好相反
  10.     if (left>=right){
  11.        // 如果最终元素仍然大于目标元素，则将索引位置往左边移动一个
  12.       if(array[left]>aim){
  13.         return left-1;
  14.       }
  15.        // 否则就是当前位置
  16.       return left;
  17.     } 
  20.        int middle = (left + right) / 2;
  21.        int value = array[middle];
  22.       if(value<aim){
  23.           // 修正 left 继续执行
  24.        return  searchIndex(array,middle+1,right,aim);
  25.       }
  26.       else{ 
  27.         // 修正 right 继续执行
  28.        return searchIndex(array,left,middle-1,aim);
  29.       }
  33.   /*  while (left < right) {
  34.       int middle = (left + right) / 2;
  35.       int value = array[middle];
  36.       if (value < aim) {
  37.         left = middle + 1;
  38.       } else {
  39.         right = middle - 1;
  40.       }
  41.     }
  42.     // #1. 如果最终元素仍然大于目标元素，则将索引位置往左边移动一个
  43.     if (array[left] > aim) {
  44.       return left - 1;
  45.     }
  46.     // 否则就是当前位置
  47.     return left;*/
  49.   }
  51.   // 插入排序
  52.   public static void insertSort(int[] array) {
  53.     // 从倒数第二位开始，遍历到底0位，遍历 N-1 次
  54.     for (int i = array.length - 2; i >= 0; i--) {
  55.       // 存储当前抽离的元素
  56.       int temp = array[i];
  57.       int index = searchIndex(array, i + 1, array.length - 1, temp);
  59.       // 根据插入的索引位置，进行数组的移动和插入
  60.       int j = i + 1;
  61.       while (j <= index) {
  62.         array[j - 1] = array[j];
  63.         j++;
  64.       }
  65.       array[j - 1] = temp;
  66.     }
  67.   }
  70.   public static void main(String[] args) {
  71.     int[] array = {9, 2, 4, 7, 5, 3};
  72.     // Arrays.toString 可以方便打印数组内容
  73.     System.out.println(Arrays.toString(array));
  74.     insertSort(array);
  75.     System.out.println(Arrays.toString(array));
  76.   }
  77. }

汉罗塔算法：

image.pngimage.png
以两个环为例，我们已经将小环移动到了B柱，最大环此时可以视为不存在。那么如第二张图所示我们将B，C柱子交换位置，那么此步骤是否和移动1阶汉诺塔一样了
然后我们中间执行了将最大环从A移动到C的固定步骤
image.png
image.png
同理，在上图为2阶汉诺塔中间的步骤之一，我们已经将最大的环移动到了C柱，最大环此时可以视为不存在。那么如右图所示我们将A,B柱子交换位置，那么接下来的步骤是否和移动1阶汉诺塔一样了呢？
到这里我们总结出了如下特点：
其实2阶汉诺塔相当于执行了三大步骤：
1.在ACB的顺序下执行了一阶汉诺塔的移法
2.从A->C移动了最大盘
3.在BAC的顺序下执行了一阶汉诺塔的移法
那么推广到三阶的时候，我们将小环和中环视为一个整体，我们是否又变成了执行二阶汉诺塔方法了呢？
那么四阶前三个环视为整体，五阶前四个环视为整体……我们已经找到了解决汉诺塔方法的递归算法。下面，我们就用代码来实现它。

  1. public class Han {
  3.     public void hanoi(int n, char A, char B, char C) {
  4.         if (n == 1) {
  5.             move(A, C);
  6.         } else {
  7.             hanoi(n - 1, A, C, B);//步骤1 按ACB数序执行N-1的汉诺塔移动
  8.             move(A, C);             //步骤2   执行最大盘子移动
  9.             hanoi(n - 1, B, A, C);//步骤3 按BAC数序执行N-1的汉诺塔移动
  10.         }
  11.     }
  13.     private void move(char A, char C) {//执行最大盘子的从A-C的移动
  14.         System.out.println("move:" + A + "--->" + C);
  15.     }
  17.     public static void main(String[] args) {
  18.         Han hanoi = new Han();
  19.         System.out.println("移动步骤：");
  20.         hanoi.hanoi(3, 'A', 'B', 'C');
  21.     }
  22. }

关于递归的四条基本法则

1.基准情形。必须有某些基准情形，它无需递归就能解出。 2.不断推进。对于那些需要递归求解的情形，每一次递归调用都必须要使求解的状况朝接近基准情形的方向推进。 3.设计法则。假设所有的递归调用都能运行。 4.合成效益法则。在求解同一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作 ——-摘自《数据结构与算法分析（机械工业出版社 Mark Allen Weiss著）》

分而治之思想——归并排序

分而治之的思想采用了递归思想，将原问题分成几个规模较小但是类似于原问题的子问题。通过递归的方式来求解这些小问题，最后将子问题的解合并来得到原问题的解。
递归 - 图13

归并排序

核心思路
将大数组分解成小数组，将每个小数组排好序，再将这些有序的小数组合并成大数组。
递归 - 图14

分——递归拆分

2分法拆分原数组，直到每个数组只有一个元素。
核心逻辑：

  1. 如何递归进行数组拆分
  2. 如何用原始数组创建两个子数组
  3. // 拷贝原数组的部分内容，从 left 到 right
  4. public static int[] subArray(int[] source, int left, int right) {
  5.     // 创建一个新数组
  6.     int[] result = new int[right - left];
  7.     // 依次赋值进去
  8.     for (int i = left; i < right; i++) {
  9.         result[i - left] = source[i];
  10.     }
  11.     return result;
  12. }
  14. // 归并排序，返回排好序的数组
  15. public static int[] mergeSort(int[] array) {
  16.     // 为了方便查看结果，我们将每个数组进行打印
  17.     System.out.println(Arrays.toString(array));
  18.     if (array.length == 1) {
  19.         return array;
  20.     }
  22.     int middle = array.length / 2;
  23.     // #1. 处理 0 到 middle 左侧数组部分
  24.     int[] left = mergeSort(subArray(array, 0, middle));
  25.     // #2. 处理 middle 到 array.length 右侧数组部分
  26.     int[] right = mergeSort(subArray(array, middle, array.length));
  28.     // TODO处理合并问题
  29.     return array;
  30. }

递归 - 图15

治——合并排序

递归 - 图16

以最后两个数组 2，4，9 和 3 ，5，7 举例。
第一步：
递归 - 图17
第二步：
递归 - 图18

  1. import java.util.Arrays;
  3. public class Sort {
  5.   // 归并排序
  6.   public static int[] mergeSort(int[] array) {
  7.     // 为了方便查看结果，我们将每个数组进行打印
  8.     if (array.length == 1) {
  9.       return array;
  10.     }
  12.     int middle = array.length / 2;
  13.     // 处理 0 到 middle 左侧数组部分
  14.     int[] left = mergeSort(subArray(array, 0, middle));
  15.     // 处理 middle 到 array.length 右侧数组部分
  16.     int[] right = mergeSort(subArray(array, middle, array.length));
  18.     // TODO处理合并问题
  19.     int l = 0;
  20.     int r = 0;
  21.     int index = 0;
  22.     // 依次比较左右两个数组
  23.     while (l < left.length && r < right.length) {
  24.       array[index] = Math.min(left[l], right[r]);
  25.       index++;
  26.       if (left[l] < right[r]) {
  27.         l++;
  28.       } else {
  29.         r++;
  30.       }
  31.     }
  33.     // 右侧数组已经遍历完成，左侧有剩余
  34.     if (l < left.length) {
  35.       for(int i = l; i < left.length; i++){
  36.         array[index] = left[i];
  37.         index++;
  38.       }
  39.     }
  41.     // 左侧数组已经遍历完成，右侧有剩余
  42.     if(r < right.length){
  43.       for(int i = r; i < right.length; i++){
  44.         array[index] = right[i];
  45.         index++;
  46.       }
  47.     }
  48.     return array;
  49.   }
  51.   // 拷贝原数组的部分内容，从 left 到 right
  52.   public static int[] subArray(int[] source, int left, int right) {
  53.     // 创建一个新数组
  54.     int[] result = new int[right - left];
  55.     // 依次赋值进去
  56.     for (int i = left; i < right; i++) {
  57.       result[i - left] = source[i];
  58.     }
  59.     return result;
  60.   }
  62.   public static void main(String[] args) {
  63.     int[] array = {9, 2, 4, 7, 5, 3};
  64.     // Arrays.toString 可以方便打印数组内容
  65.     System.out.println("raw: " + Arrays.toString(array));
  66.     int[] result = mergeSort(array);
  67.     System.out.println("result: " + Arrays.toString(result));
  68.   }
  69. }

分而治之思想——快速排序

快速排序是现在面试官最喜欢面试的排序算法，是现在编程语言自带函数中，使用最多的算法。

实现原理

分区
image.png
递归 - 图20
image.png
第一步：
递归 - 图22
第二步：
、递归 - 图23
第二次分区
通过第一次分区，我们将数组分为左侧和右侧，按照递归的思想，我们继续将左右两侧数组按照选轴分区重复排序。
**递归 - 图24

时间复杂度

每次分区需要全数组比较一次所以为O（N），而又要进行O（log（N））次分区，所以最终结果为O（Nlog（N））
最坏的情况：数组本身是有序的。
递归 - 图25
每次分区，实际上没有分区，因为轴的值永远是最大值，这个时候时间复杂度为O（N^2）

代码实现

  1. import java.util.Arrays;
  3. public class QuickSort {
  5.   // 快速排序
  6.   public static void quickSort(int[] array) {
  7.     // 调用快速排序的核心，传入left，right
  8.     quickSortCore(array, 0, array.length - 1);
  9.   }
  11.   // 快速排序的核心，同样也是递归函数
  12.   public static void quickSortCore(int[] array, int left, int right) {
  13.     // 递归基准条件，left >= right 即表示数组只有1个或者0个元素。
  14.     if (left >= right) {
  15.       return;
  16.     }
  17.     // 根据轴分区
  18.     int pivotIndex = partition(array, left, right);
  20.     // 递归调用左侧和右侧数组分区
  21.     quickSortCore(array, left, pivotIndex - 1);
  22.     quickSortCore(array, pivotIndex + 1, right);
  23.   }
  25.   // 对数组进行分区，并返回当前轴所在的位置
  26.   public static int partition(int[] array, int left, int right) {
  27.     int pivot = array[right];
  29.     int leftIndex = left;
  30.     int rightIndex = right - 1;
  31.     while (true) {
  32.       // 左指针移动
  33.       while (array[leftIndex] <= pivot && leftIndex < right) {
  34.         leftIndex++;
  35.       }
  36.       // 右指针移动
  37.       while (array[rightIndex] >= pivot && rightIndex > 0) {
  38.         rightIndex--;
  39.       }
  41.       if (leftIndex >= rightIndex) {
  42.         break;
  43.       } else {
  44.         swap(array, leftIndex, rightIndex);
  45.       }
  46.     }
  48.     swap(array, leftIndex, right);
  49.     return leftIndex;
  50.   }
  52.   public static void swap(int[] array, int index1, int index2) {
  53.     int temp = array[index1];
  54.     array[index1] = array[index2];
  55.     array[index2] = temp;
  56.   }
  58.   public static void main(String[] args) {
  59.     int[] array = {9, 2, 4, 7, 5, 3};
  60.     // Arrays.toString 可以方便打印数组内容
  61.     System.out.println("raw: " + Arrays.toString(array));
  62.     quickSort(array);
  63.     System.out.println("result: " + Arrays.toString(array));
  64.   }
  65. }

快速排序应用——快速选择

image.png
也就是第四大的元素。
递归 - 图27
image.png

代码实现

  1. import java.util.Arrays;
  3. public class QuickSort {
  5.   // 快速选择，返回选中的元素
  6.   public static int quickFind(int[] array, int aim) {
  7.     // 调用快速选择的核心，传入left，right
  8.     return quickFindCore(array, aim, 0, array.length - 1);
  9.   }
  11.   // 快速选择的核心，同样也是递归函数
  12.   public static int quickFindCore(int[] array, int aim, int left, int right) {
  13.     // 递归基准条件，left >= right 即表示数组只有1个或者0个元素，返回当前的元素
  14.     if (left >= right) {
  15.       return array[left];
  16.     }
  17.     // 根据轴分区
  18.     int pivotIndex = partition(array, left, right);
  19.     // 根据 aim 确定继续递归的方向
  20.     if (pivotIndex > aim) {
  21.       return quickFindCore(array, aim, left, pivotIndex - 1);
  22.     } else if (pivotIndex < aim) {
  23.       return quickFindCore(array, aim, pivotIndex + 1, right);
  24.     } else {
  25.       return array[pivotIndex];
  26.     }
  27.   }
  29.   // 对数组进行分区，并返回当前轴所在的位置
  30.   public static int partition(int[] array, int left, int right) {
  31.     int pivot = array[right];
  33.     int leftIndex = left;
  34.     int rightIndex = right - 1;
  35.     while (true) {
  36.       // 左指针移动
  37.       while (array[leftIndex] < pivot && leftIndex < right) {
  38.         leftIndex++;
  39.       }
  40.       // 右指针移动
  41.       while (array[rightIndex] > pivot && rightIndex > 0) {
  42.         rightIndex--;
  43.       }
  45.       if (leftIndex >= rightIndex) {
  46.         break;
  47.       } else {
  48.         swap(array, leftIndex, rightIndex);
  49.       }
  50.     }
  52.     swap(array, leftIndex, right);
  53.     return leftIndex;
  54.   }
  56.   public static void swap(int[] array, int index1, int index2) {
  57.     int temp = array[index1];
  58.     array[index1] = array[index2];
  59.     array[index2] = temp;
  60.   }
  62.   public static void main(String[] args) {
  63.     int[] array = {72, 77, 48, 17, 71, 2, 25, 97, 82, 5, 2, 18, 15, 57, 7, 48, 93, 47, 38, 74, 18, 93, 98, 41, 54, 4, 47, 4, 63, 76};
  64.     System.out.println("raw: " + Arrays.toString(array));
  65.     // 目标是倒数第 6 个元素
  66.     int result = quickFind(array, array.length - 6);
  67.     System.out.println("result: " + result);
  68.      System.out.println("after: " + Arrays.toString(array));
  69.   }
  70. }