算法——递归

背景

最近遇到一个类似爬楼梯的算法题。索性对递归的处理总结一下。

爬楼梯题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入：2
输出：2
解释：有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶示例 2：输入：3
输出：3
解释：有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解法1

int climbStairs(int n) {
    if(n == 1) return 1;
    else if(n == 2) return 2;
    else return climbStairs(n-1) + climbStairs(n-2);
}

解法2（递归代码要警惕重复计算）

 Map<Integer,Integer> map = new HashMap();
public int climbStairs(int n) {
    if(n==1) return 1;
    else if(n == 2) return 2;
    else if(map.containsKey(n)) return map.get(n);
    else {
        int result = climbStairs(n-1) + climbStairs(n-2);
        map.put(n,result);
        return result;
    }
}

解法3（改非递归）

public int climbStairs(int n) {
    if(n == 1) return 1;
    if(n == 2) return 2;
    int pre2 = 1;
    int pre1 = 2;
    int result =0;
    for(int i=3;i<=n;i++){
        result = pre1+pre2;
        pre2 = pre1;
        pre1 = result;
    }
    return result;
}

总结

如上，这道题目的解法主要还是应用了递归的编程技巧。递归，去的过程称为“递”，回来的过程称为“归”。一般所有的递归问题都可以用递归公式来解决。写出递归公式，问题就解决了一多半。

f(n) = f(n-1)+1 其中 f（1）=1

递归需要满足的三个条件

1. 一个问题的解可以分解为几个子问题的解；又想起曾经学过的那篇初中课文《走一步，再走一步》，这就是分解子问题的过程。当一个人目标意识太强的时候，很容易迷失自我。其实我们求解递归问题，以为是如此，我们求解当前问题的值，或许只是上一个问题的值+1；
2. 这个问题与分解后的子问题，除了数据规模不同，求解思路一样；
3. 存在递归终止条件；

防止堆栈溢出

在jvm中，“栈”又称“堆栈”。每个方法在执行的过程中都会创建一个栈帧用于存储局部变量表、操作数栈、动态链接、方法出口等信息。每一个方法从调用直至执行完成的过程，就对应着一个栈帧在虚拟机栈中入栈到出栈的过程。如果递归深度多大，导致栈不够用，就会导致 StackOverflowError。如解法1，当n足够大，就会导致这个问题。

如何尽量避免？

• 限制递归深度；比方说当递归深度到达100的时候，就停止递归。但这种方法应用条件较为苛刻，对于一些对结果要求不严格的业务才可使用。
• 递归代码要警惕重复计算；(解法2) 比方说f（5）= f(4)+f(3)需要计算f(4)和f(3)，那么我们计算f(4) = f(3)+f(2)还需要计算f(3)。f(3)被计算了2次，这个就是重复计算。避免重复计算可以使用散列表等数据结构将曾经计算过的结果缓存起来。
• 递归代码改非递归代码；（解法3） 很多递归代码都可以使用循环迭代的方式来替换，这样就解决了频繁压栈带来的溢出问题；
• 自己实现栈；在虚拟机中栈的深度受栈帧大小影响，当前可用深度不好确定。不如我们自己实现一个栈，对每个计算结果压栈，用到计算参数时，再出栈。整个过程就由我们自己控制了；

时间复杂度

解法1在实际应用中很容易超时，因为时间复杂度太高。那么怎么计算递归算法的时间复杂度呢？其实在所有的递归问题中，因为是大问题拆分小问题的思路，所以整个计算过程算下来就好像是一棵树。

假定加法时间复杂度忽略为1，那么第一层做加法1次，为1；第二次做2次，为2，第三层做4次为4...。这棵树最高为n，最低为n/2；当高为n时，所有层加和为2n-1,当高为n/2时，所有层加和为2n/2-1,无论如何，它的时间复杂度为指数级的，当n足够大时，是很恐怖的。这就是利用递归树求解递归的时间复杂度。

以上。。。

王争 《数据结构和算法之美》