数据结构与算法之递归

何为递归？

所谓递归，简单点来说，就是一个函数直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
我们可以把” 递归 “比喻成 “查字典 “，当你查一个词，发现这个词的解释中某个词仍然不懂，于是你开始查这第二个词。可惜，第二个词里仍然有不懂的词，于是查第三个词，这样查下去，直到有一个词的解释是你完全能看懂的，那么递归走到了尽头，然后你开始后退，逐个明白之前查过的每一个词，最终，你明白了最开始那个词的意思。（摘自知乎的一个回答）

递归函数

所谓递归函数是自身调用自身，在执行递归函数时，系统会把递归函数的全部信息压入栈中，且每次进行子操作时，栈会记录当前操作的变量，待子操作完成时恢复最初的现场。总之，一切非递归函数皆可转换为递归函数。

递归函数的复杂度

T(n) = aT(n/b) + O(n ^d)

• 1. log(b,a) > d ===> 复杂度为O(n^ log(b,a))
• 2.log(b,a) = d ===> 复杂度为O(n^d * logN)
• 3.log(b,a) < d ===> 复杂度为O(n^d)
  其中，T(n) 表示数据样本量为n时的时间复杂度，aT(n/b)表示自操作的时间复杂度，其中a表示子操作次数，n/b表示子操作的数据样本量，O(n^d)表示除去子操作外常规的比较时间的时间复杂度。注意，使用上述函数的前提是子操作的样本量应该相等。

举列说明：求数组的最大值

public class Recursion {
    public static int getMax(int []arr, int L, int R ) {
          if(L == R) {
              return arr[L];
          }
          int mid = (L+R)/2;
          int maxLeft = getMax(arr, L, mid);
          int maxRight = getMax(arr, mid+1, R);
          return Math.max(maxLeft, maxRight);
    }
}

上述递归函数中，将一个数组划为左右两部分进行查找最大值，然后进行比较，得出数组的最大值，可以看出，每次子操作的样本量为n/2,总共左右两次操作，d=0,常规的比较时间为O(1),故本次递归函数的时间复杂度为T(n) = 2(n/2) + O(1);