分治递归思想

为了解决一个给定的问题，算法一次或多次递归的调用自身以解决若干子问题，上层函数调用子函数需要等子函数运行完，这些就是典型的分治法的思想。我们将原问题分解为几个规模较小但类似于原问题的子问题，从而递归的调用自身，最后合并这些子问题的解来建立原问题的解。

关键：1，递：分解原问题为相同结构的子问题。2，解决这些子问题。3，归：合并子问题的解。

注意：调用太深了就可能会堆栈溢出，需要考虑堆栈的深度。

经典案例

递归求和

如果计算1 + 2 + … n ，可以用递归的方法来写。

1
2
3

int AddFrom1ToN_Recursive(int n){
	return n <= 0?: 0:n + AddFrom1ToN_Recursive(n-1);
}

但这里递归比循环的时间复杂度更高，函数递归调用自身都要在内存栈中分配空间保存参数（如n到哪了），返回地址（函数的地址），临时变量（上一次计算得到的AddFrom1ToN_Recursive值）等等，因此空间和时间消耗较多。

更严重的话递归会带来调用栈溢出的问题，递归调用层级太多就有可能超出栈的容量。

归并排序。

排序—归并排序)

归并排序的详细复杂度分析见《算法导论》P21，通过递归树分析，总代价是$cnlgn + cn$ (c表示求解规模为1的问题所需要的时间以及在分解步骤与合并步骤处理每个数组元素所需要的时间。)

题目

leecode84

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。

分析：最大面积是最矮柱子以后，矩形的宽尽可能往两边延伸；or 最矮柱子左边的最大面积矩形 or 最矮柱子右边的最大面积矩形。

int calculateArea(vector<int>& height,int start, int end){
    if (start > end) {
        return 0;
    }
    int minindex = start;
    for (int i=start; i<=end; i++) {
        if (height[minindex] > height[i]) {
            minindex = i;
        }
    }
    return max(height[minindex]*(end-start+1) ,max( calculateArea(height,start,minindex-1), calculateArea(height,minindex+1,end)) );
}

int largestRectangleArea(vector<int>& height){
    return calculateArea(height, 0, height.size()-1);
}

int main_recursive(){
    vector<int> nums = {2,1,5,6,2,3};
    cout<<largestRectangleArea(nums)<<endl;
    return 0;
}

还有很多二叉树类的问题都涉及到递归方法。

Reference

1, 《算法导论》机械工业出版社第三版（黑皮的，Thoms H Cormen…）

2，leecode网站

3，https://www.bilibili.com/video/BV1954y1Q7u8/