下面用LeetCode上的一个爬楼梯问题给出递归和分治两种解法来对比。

假设你正在爬楼梯，需要n阶才能到达楼顶（n是一个正整数），每次你可以爬1或2个台阶，有多少种不同的方法可以爬到楼顶？

这个问题每走3阶就要重新选择爬1阶或者两阶，很明显我们可以把一个大问题拆解成一个一个的小问题，可以使用递归来解决。
递归方程式：f(n) = f(n-1)+f(n-2)
递归的结束条件是我们已知的：f(1) = 1; f(2) = 2;
代码如下：

int upStairs1(int n) {
    
    if (n < 1) return 0;
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    return upStairs1(n-1)+upStairs1(n-2);
}

使用动态规划法，开辟n+1个内存空间来存储每一步的值：

int upStairs2(int n) {
    
    if (n == 1) return 1;

    int *times = (int *)malloc(sizeof(int)*(n+1));
    times[0] = 0;
    times[1] = 1;
    times[2] = 2;

    for (int i = 3; i < n+1; i++) {
        times[i] = times[i-1]+times[i-2];
    }
    
    return times[n];
}

两种算法的时间复杂度：递归的时间复杂度是n的平方，分治法复杂度为n。从空间角度来看，使用递归，多个函数嵌套调用，系统会开辟一个“递归工作栈”作为整个函数运行期间的数据存储，空间上的耗费是很大的，而分治法则只需要开辟一段存储空间来存储整形数据。综合来看，我们还是要尽量避免递归的使用。动态规划法是个很好的选择。