递归算法

2018-09-25 本文已影响50人 dlihasa

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

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

递归算法解决如下：

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);
    }

}

运行结果如下：

栗子中，把目标数组分成左右两组的思路将大问题分成子问题，不断地按照分成两组的思路继续下分，最终有一个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出栈，还原现场，继续执行下边的流程