递归算法

我们先用递归算法来解决一个小问题，当然这个小问题不必用算法来解，只是为了对递归做个说明。

问题：在一个数组中找出最大的数。

递归算法解决如下：

public class Recursion {

    public static void main(String[] args) {
        int[] arr = {3,1,4,6,9,8,10,23,14};
        System.out.println(getMax(arr,0,arr.length-1));
    }
    
    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);
    }

}

运行结果如下：

23

栗子中，把目标数组分成左右两组的思路将大问题分成子问题，不断地按照分成两组的思路继续下分，最终有一个if的条件语句作为递归的条件终结。上述就是递归的两个关键点：大问题划分为子问题、最终有一个条件结束递归。

那么递归的内部执行到底是什么呢？其实方法调用都存在压栈出栈的问题，假如数组为{4,1,2,3}，
【A】首次执行，L=0，R=3，L不等于R，mid为(0+3)/2=1,执行到maxLeft这行代码，此时需要执行子方法getMax()（递归中就是自身）,那么此时会做一个方法压栈（就是将此时方法执行到哪一行、一些变量如mid是多少，L是几，R是几这些所有有关信息保存到方法栈中，L=0，R=3，mid=1，执行到x行）。
【B】这些做好之后就会执行该子方法getMax，L=0，R=1，L不等于R，mid为(0+1)/2=0，再次执行到maxLeft这行代码，重复上述过程，方法压栈（L=0，R=1，mid=0，执行到x行）。
【C】这些做好之后就会执行子方法getMax，L=0，R=0，L等于R，return arr[0]，返回4。
然后将B出栈，还原现场，继续执行下边的流程

下面我们通过断点来直观地观察一下这个执行过程，数组采用{3,2,4,5}这样一个小数组来方便查看过程（上面图片依次为代码执行到的位置、方法栈、此时方法内各变量的值）：

• 第一轮

  
  首次执行代码部分.png
  首次进入getMax，方法栈情况.png
  此时方法内各变量的值.png

• 第二轮

  
  第二次进入getMax，并执行到了getMax这个位置.png
  将上次执行到的getMax压栈，并再次执行到16行.png
  此时的各变量值.png

• 第三轮

  
  此次if条件成立，代码执行到12行.png
  第三次getMax压栈if条件成立.png
  此时变量.png

• 第四轮

  
  条件满足跳出getMax，回到调用处.png
  将执行完的getMax方法出栈.png
  还原现场（将出栈方法压栈时保存的信息还原）.png

到第四轮有出栈的情况了，出栈完成之后，就会顺着上次执行到的位置往下执行，因为本次递归调用结束了，需要将本次下方的代码继续执行，执行完下方代码之后才算是执行了本次流程，然后才能返回到上次调用的位置继续执行。

整体的执行过程不再一一截图了，写一份代码debug看一下这三张图展示的信息细细想来也就理解了。

递归方法的时间复杂度比较复杂

归纳一个表达式（master公式）：T(N)=aT(N/b)+O(N^d)
栗子中套入上述表达式为2T(N/2)+O(1)

剖析递归行为和递归行为时间复杂度的估算

master公式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)

所有的递归都可改为非递归，无非就是系统帮我们压栈改为我们自己压栈。

注：还有另外一个表达式不在阐述。大部分都可以用上述表达式计算。