递归

概述

递归很多网上简单的说法就是：自己调用自己。其实递归不是玄学，它是有理论支撑的—系统栈。

例子：求数组中最大数的递归方法

求数组arr[L...R]中的最大值，怎么用递归方法实现。

• 将[L...R]范围分成左右两半。左：[L...Mid]，右：[Mid + 1...R]
• 求左部分求最大值，右部分求最大值
• [L...R]中的最大值，是max{左部分求最大值，右部分求最大值}

第二步，是个递归过程，当范围只有一个数，就可以不用在递归了。

public class GetMax {

  public static int getMax(int[] arr) {
    return process(arr, 0, arr.length - 1);
  }

  // arr[L..R]范围上求最大值  L ... R   N
  public static int process(int[] arr, int L, int R) {
    // arr[L..R]范围上只有一个数，直接返回
    if (L == R) { 
      return arr[L];
    }
    // L...R 不只一个数，mid = (L + R) / 2
    int mid = L + ((R - L) >> 1);
    int leftMax = process(arr, L, mid);
    int rightMax = process(arr, mid + 1, R);
    return Math.max(leftMax, rightMax);
  }

}

递归脑图和实际实现

对于新手来说，在分析递归函数的时候，把调用的过程画出结构图（递归函数脑图，即递归调用树），这有利于分析递归。

递归底层是利用系统栈实现的。

任何递归函数都一定可以改成非递归。

时间复杂度-Master公式

master公式：$T(N) = a \cdot T(\frac{N}{b}) + O(N^d)$

N：父问题的样本量
N/b：子问题的样本量, 划分为子问题的规模
a：子问题调用的次数
O(N^d)：其他的步骤复杂度

1. $log_{b}a$ > d -> 复杂度为 $O(N^{log_{b}a})$
2. $log_{b}a$ = d -> 复杂度为 $O(N^d \cdot logN)$
3. $log_{b}a$ < d -> 复杂度为 $O(N^d)$

master公式的适用范围：父问题划分为子问题的规模是一样的。

例如，上面的例子求数组中最大数的递归方法，它的父问题的样本量为N，子问题的规模为 N/2，调用次数a为2，除了递归调用外的操作的时间复杂度为$O(1)$，所以d=0。

所以它的Master公式为$T(N) = 2\cdot T(\frac{N}{2}) + O(N^0)$，符合$log_{2}2$ > 0，所以它的时间复杂度为$O(N^{log_{2}2}) = O(N)$。