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];
    }
};

这样一来，原本需要递归才能解决的问题，直接变成查表法了，时间空间复杂度一下子均变为 o(1)。

我们看看 30 阶台阶时有多少种走法呢？

　　fn(30) = 53798080

超过 5千万，这更加验证了人是无法完成这样庞大的计算的。

 

爬楼梯：力扣第 70 题。

利用查表法，让我们看看战绩：

　　　　

 

现在总结递归算法及一些需要注意的地方：

　　1. 递归需要满足的三个条件：

　　　　a. 一个问题的解可以分解为几个子问题的解。

　　　　b. 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样。

　　　　c. 存在递归终止条件。

　　2. 如何编写递归代码：

　　　　a. 找到如何将大问题分解为小问题的规律。

　　　　b. 基于此写出递推公式。

　　　　c. 再推敲终止条件。

　　　　d. 最后将递推公式和终止条件翻译成代码。

　　3. 递归代码要警惕堆栈溢出

　　4. 怎么将递归代码改写为非递归代码 或 如何优化递归代码

　　5. 递归有利有弊：

　　　　利是递归代码的表达力很强，写起来非常简洁。

　　　　弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。

 

关于递归算法到此暂时结束，关于其优化以及将递归转化为非递归本文并未深入讲解，这在以后会多次讲解到。