递归是如何实现的

举例来说，比如我们希望求一个数组中的最大值，使用如下递归的方法

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

    // arr[l....r]范围上的最大值
    public static int f(int[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }
        int m = (l + r) / 2;
        int lmax = f(arr, l, m);
        int rmax = f(arr, m + 1, r);
        return Math.max(lmax, rmax);
    }

    public static void main(String[] args) {
        int[] arr = { 3, 8, 7, 6, 4, 5, 1, 2 };
        System.out.println("数组最大值 : " + maxValue(arr));
    }

每次将数组对半划分，求出对半划分两部分的最大值，取其中较大者返回

递归的实现

递归调用图

由于递归的调用就是通过栈来实现的，我们也可以不使用系统栈，而自己将递归的中间结果压入栈，因此，任何递归都可以改为非递归实现。递归改成非递归的必要性：
1）工程上几乎一定要改，除非确定数据量再大递归也一定不深，如归并排序、快速排序、线段树、很多的平衡树等；
2）算法笔试或者比赛中（能通过就不改）

master公式

首先给出公式T（N）=a*T（N/b）+O（n^c），a，b，c都是常数
以上面的代码为例，解释这个公式的使用

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

    // arr[l....r]范围上的最大值
    public static int f(int[] arr, int l, int r) {
        if (l == r) {
            return arr[l];
        }
        int m = (l + r) / 2;
        int lmax = f(arr, l, m);
        int rmax = f(arr, m + 1, r);
        return Math.max(lmax, rmax);
    }

    public static void main(String[] args) {
        int[] arr = { 3, 8, 7, 6, 4, 5, 1, 2 };
        System.out.println("数组最大值 : " + maxValue(arr));
    }

f为递归函数，其内部对自身有两次调用，即lmax=f（arr，l，m）和rmax=f（arr，m+1，r），故a=2。而由于是每次将数组对半划分，再调用f，因此b=2。f函数内部的操作都是时间复杂度为O（1）的操作，因此c=0。因此我们求出了a=2，b=2，c=0，再来就可直接得出时间复杂度

master公式时间复杂度

补充情况