首页 > > 程序设计 > C/C++ >

DSA_07：递归算法

2020-03-30 08:02:01来源：博客园阅读 ()

DSA_07：递归算法

前面讲解了复杂度分析、数组、链表、栈、队列，今天讲解递归算法。

递归，可以说同前面这些基础数据结构一般用途广泛，在诸多算法中，这是非常基础，常用的。

简单举几个例子：

　　1. 二叉树前序、中序、后续遍历可用递归。

　　2. 深度优先算法可以递归，如迷宫寻路、迷宫生成等。

　　3. 快排、归并排序可用递归。

　　4. 二分查找可用递归。

　　5. 解决实际问题时可用递归。

同样，递归的用途也是多不胜数。想要正确、灵活去应用该算法，需要掌握其一些特性。

本文通过一个基础的例子学习该算法，并给出该算法的各种特性技巧。

例：这里有 N 阶台阶，你一次可以跨越 1阶、2阶或 3阶，那么，你有多少种不同的走法走完这 N 阶台阶呢？

如果你曾遇到过该题，你会觉得非常简单。但是如果你不会递归，你会觉得非常困难，用人脑几乎不可能想清楚，后面会给出解释。

这里直接给出方法：

　　走完这 N 阶有多少种走法？然后你一次可以跨越 1~3 阶，令走完这 N 阶有 F(N) 种方法。

　　则走到 N 阶的路径是否等于：走到 N-1 阶的方法 + 走到 N-2 阶的方法 + 走到 N-3 阶的方法？

　　当然是的，这里或许需要花费时间细细品味一下。

　　你可以理解：走到 N 阶可以从 N-1 阶上去，也可从 N-2 阶上去，还可以从 N-3 阶上去，这样说是否理解了呢？

因此有 F(n) = F(n-1) + F(n-2) + F(n-3)。

终止条件呢：F(1) = 1，F(2) = 2，F(3) = 4。相信这能够想清楚。

因此有下面代码：

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

现在，让我们看看该算法的分解图：

你是否发现问题了呢？

　　　　F(4) 被重复计算了！！！

随着 N 的增加，被重复计算的会越来越多，性能开销太大！！！

回过头看，为何人脑无法处理过来呢？你可以看出，其复杂是 O(3^n)，仅次于阶乘复杂度，你的大脑能承受这样的指数爆炸吗？

递归会占用栈内存，对空间的开销非常大，小心爆栈。

递归算法如何优化呢？一方面是将递归用迭代法写，另外可用尾递归优化，这里不再细说。

在力扣等地方刷题时有时间限制，它会给出大量的测试数据，我们有什么办法使得运行时间非常小呢？

就本题而言，如果告诉你，台阶最多 30 阶，请看代码：

class Solution
{
public:
    Solution() { gen(); }
    int Fn(int n)
    {
        if (n <= 0 || n > 30) return -1;
        return val[n - 1];
    }

private:
    int val[30];
    void gen()
    {
        val[0] = 1;
        val[1] = 2;
        val[2] = 4;
        for (int i = 3; i < 30; ++i)
            val[i] = val[i - 1] + val[i - 2] + val[i - 3];
    }
};