递归 vs. 迭代 & 动态规划

小咪咪 2022-08-08 11:47 204阅读 0赞

对[程序员][Link 1]来说，递归应该是一个与生俱来的思想（a built-in thought），可以通过一个简单的例子来说明。

问题： 有n步台阶，一次只能上1步或2步，共有多少种走法。

步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。

为了走完n步台阶，只有两种方法：从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数，那么f(n) = f(n-1) + f(n-2)。

步骤2: 确保开始条件是正确的。

f(0) = 0;  
f(1) = 1;

public static int f(int n){
        if(n <= 2) return n;
        int x = f(n-1) + f(n-2);
        return x;
    }

递归方法的时间复杂度是n的指数级，因为有很多冗余的计算，如下：

f(5)  
f(4) + f(3)  
f(3) + f(2) + f(2) + f(1)  
f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)  
f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)

直接的想法是将递归转换为迭代：

public static int f(int n) {
    
        if (n <= 2){
            return n;
        }
    
        int first = 1, second = 2;
        int third = 0;
    
        for (int i = 3; i <= n; i++) {
            third = first + second;
            first = second;
            second = third;
        }
    
        return third;
    }

对这个例子而言，迭代花费的时间更少，你可能也想看看Recursion vs Iteration。

## 动态规划 ##

动态规划是解决下面这些性质类问题的技术：

1.  一个问题可以通过更小子问题的解决方法来解决（译者注：即问题的最优解包含了其子问题的最优解，也就是最优子结构性质）。
2.  有些子问题的解可能需要计算多次（译者注：也就是子问题重叠性质）。
3.  子问题的解存储在一张表格里，这样每个子问题只用计算一次。
4.  需要额外的空间以节省时间。

爬台阶问题完全符合上面的四条性质，因此可以用动态规划法来解决。

public static int[] A = new int[100];
    
    public static int f3(int n) {
        if (n <= 2)
            A[n]= n;
    
        if(A[n] > 0)
            return A[n];
        else
            A[n] = f3(n-1) + f3(n-2);//store results so only calculate once!
        return A[n];
    }

转载来自：[http://www.codeceo.com/article/10-algorithms-in-programming-interview.html][http_www.codeceo.com_article_10-algorithms-in-programming-interview.html]

[Link 1]: http://www.codeceo.com/
[http_www.codeceo.com_article_10-algorithms-in-programming-interview.html]: http://www.codeceo.com/article/10-algorithms-in-programming-interview.html