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. 递归有利有弊：
利是递归代码的表达力很强，写起来非常简洁。
弊就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。
关于递归算法到此暂时结束，关于其优化以及将递归转化为非递归本文并未深入讲解，这在以后会多次讲解到。