上一篇，我们聊了什么是递归，那么这一篇我们就聊一下什么是递推。
读这篇文章之前，不要有什么压力，递推很符合咱们正常人的逻辑不难。
同样，我们先从一个故事讲起吧。
在一个遥远的王国里，有一个著名的数学家名叫阿基米德。他是国王最信任的顾问，因为他对数学有着深刻的理解。有一天，国王遇到了一个难题，他想知道王国内所有道路的长度总和。然而，这个王国非常大，道路错综复杂，要测量每条道路的长度几乎是不可能的任务。
阿基米德思考了一会儿，然后提出了一个聪明的办法。他设计了一个递推公式，只需要知道每个村庄之间的道路数量和每条道路的平均长度，就能够计算出整个王国的道路总长度。
在王国的中心，有一个最大的村庄，我们称之为“中心村”。从中心村出发，有五条道路分别通向其他五个村庄。每个村庄又有若干条道路通向其他村庄。阿基米德决定从中心村开始，逐步向外递推，计算所有道路的总长度。
首先，阿基米德计算了中心村到其他五个村庄的道路长度。然后，他告诉每个村庄的长老，如何计算从他们村庄出发到其他村庄的道路长度。
计算的过程：
中心村到其他五个村庄的道路长度已知，记为L1。
每个村庄的长老收到阿基米德的指示，计算从他们村庄出发到相邻村庄的道路长度，然后将这些长度加起来，得到该村庄的总道路长度。
举个🌰： 例如，假设有一个村庄A，它有两条道路分别通向村庄B和村庄C。阿基米德会告诉村庄A的长老：“你知道中心村到A的道路长度是La，现在你需要做的是，计算从A到B和A到C的道路长度，然后加起来，这就是从中心村通过A到达B和C的总道路长度。”
每个村庄的长老都按照阿基米德的指示去做，他们计算了自己村庄的道路长度，然后报告给阿基米德。阿基米德将这些长度加起来，得到了整个王国的道路总长度。
村庄B的长老计算了从B到其他村庄的道路长度，加上从中心村到B的道路长度。
村庄C的长老也做了同样的事情。
这样一直递推下去，直到所有村庄的道路长度都被计算出来。
最终，阿基米德将所有村庄的报告汇总起来，得出了王国内所有道路的总长度。国王对阿基米德的智慧感到非常惊讶和感激，因为他不仅解决了看似无解的问题，而且还设计了一个简单有效的递推方法。
这个故事呢，充分展示了递推的概念，即通过已知的初始条件，逐步计算出后续的结果，直到得到最终答案。
下面，我们进入正题，苦涩的知识概念就要来了。
递推
递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。 —摘自《百度词条》
简单的来说，它依赖于重复的运算过程来逐步构建问题的解决方案。递推算法通过已知的初始值或基础情况，利用某种关系或规则来计算后续的值，直到达到特定的目标或条件。
关键概念：
初始值或基础情况：递推算法通常从一个或多个已知的初始值开始，这些值作为算法迭代的起点。
递推关系：这是定义如何从一个或多个前驱值推导出后续值的关系。这个关系可以是简单的数学运算，也可以是更复杂的逻辑或规则。
迭代：递推算法通过迭代的方式，重复应用递推关系来逐步接近最终结果。
终止条件：递推算法需要一个明确的终止条件，以确定何时停止迭代过程。这个条件可以是达到特定的值、满足某个条件或完成一定数量的迭代。
步骤包括：
设置初始值或基础情况。
定义递推关系。
迭代应用递推关系，直到满足终止条件。
输出结果。
应用：
数值计算：
计算数列的项，如斐波那契数列、阿姆斯特朗数等。
计算数学函数的值，例如，用泰勒级数来近似计算 exe^xex、sin(x)sin(x)sin(x) 等。
算法设计：
搜索算法中的广度优先搜索（BFS）和深度优先搜索（DFS）中使用递推来遍历图。
排序算法，如冒泡排序、选择排序和插入排序等，都是通过迭代来比较和交换元素。
动态规划：
解决最优化问题，如背包问题、最长公共子序列、最短路径问题等。
计算矩阵链乘问题中的最优括号化。
图形学：
渲染算法中的光线追踪，通过递推计算光线与场景的交点。
图形渲染管线中的像素处理和着色器计算。
日常编程：
数据处理中的循环，如遍历数组、列表或数据库中的记录。
文件读写操作，逐行或逐块处理数据。
数学证明：
证明数学定理，如通过数学归纳法，先证明基础情况，然后假设对某个 nnn 成立，证明对 n+1n+1n+1 也成立。
递归 VS 递推
通过一个表格，对比一下递归和递推的不同特点：
特点
递归（Recursion）
递推（Iteration）
定义
递归是一种编程技巧，一个函数直接或间接地调用自身。
递推是一种算法设计方法，通过迭代的方式逐步构建结果。
调用
递归函数会不断地自我调用，直到达到某个终止条件。（从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，即顺推法的逆过程。）
递推通常使用循环结构，如for循环或while循环，没有自我调用。（递推算法是一种用若干步可重复运算来描述复杂问题的方法。递推是序列计算中的一种常用算法。）
状态
递归通过函数的调用栈来保持状态，每次调用都会创建新的执行上下文。
递推通常在同一个执行上下文中，通过变量的更新来保持状态。
内存
递归可能导致大量的内存使用，因为每次函数调用都需要额外的栈空间。
递推通常使用更少的内存，因为它不需要额外的调用栈。
性能
递归可能会导致性能问题，特别是在深度递归时，因为栈溢出的风险。
递推通常在性能上更优，因为它避免了函数调用的开销。
可读性
递归代码往往更简洁，易于理解，尤其是对于具有自然递归结构的问题。
递推代码可能更复杂，需要更多的循环和状态管理。
适用场景
递归适用于解决可以分解为更小、更简单的子问题的问题，如树遍历、分治算法等。
递推适用于需要按步骤迭代处理的问题，如数组遍历、累加计算等。
示例
斐波那契数列的计算、二叉树的遍历。
累加器、循环打印数组元素。
例题
爬楼梯
问题描述： 假设你正在爬楼梯，每次你可以爬1个或2个台阶，问有多少种不同的方法可以爬到n阶楼顶。
步骤 1：定义问题： 设f(n)表示爬到第n阶楼梯的方法数。
步骤 2：找出基础情况：
当n=1n=1n=1时，只有一种方法可以爬到第一阶，即直接爬一阶。所以f(1) = 1。
当n=2n=2n=2时，有两种方法可以爬到第二阶，一是先爬一阶再爬一阶，二是直接爬两阶。所以f(2) = 2。
步骤 3：找出递推关系： 对于n>2n > 2n>2的情况，爬到第n阶的方法可以从第n-1阶爬上来，或者从第n-2阶爬上来。因此，爬到第n阶的方法数是爬到第n-1阶和第n-2阶方法数的和。
这可以表示为递推公式： f(n) = f(n-1) + f(n-2)
步骤 4：解释递推关系：
f(n-1) 表示到达第n-1阶的方法数，从第n-1阶到第n阶只需再爬一阶。
f(n-2) 表示到达第n-2阶的方法数，从第n-2阶到第n阶需再爬两阶。
步骤 5：实现递推算法： 可以使用循环或递归来实现这个递推公式。以下是使用循环的实现方式：
#include
typedef long long LL;
LL climbStairs(LL n) {
if (n == 1) return 1;
if (n == 2) return 2;
LL a = 1; // f(n-2)
LL b = 2; // f(n-1)
LL c = 0; // f(n)
for (LL i = 3; i <= n; ++i) {
c = a + b; // f(n) = f(n-1) + f(n-2)
a = b; // 更新f(n-2)为下一轮的f(n-1)
b = c; // 更新f(n-1)为下一轮的f(n)
}
return c; // 返回f(n)
}
int main() {
LL n;
std::cin >> n;
LL ways = climbStairs(n);
std::cout << ways << std::endl;
return 0;
}
对于爬楼梯问题，使用递推方法的时间复杂度已经是 O(n)O (n)O(n)，这是最优的时间复杂度，因为每个楼梯数的结果都依赖于前两个楼梯数的结果，必须至少遍历一次从 3 到 n 的所有楼梯数来得到最终结果。
Catalan数
卡特兰数（Catalan number）是一组著名的数列，它在组合数学中有着广泛的应用。卡特兰数通常用来解决括号匹配、二叉树计数、多边形划分等问题。
第n个卡特兰数记为CnC_nCn，它的递推公式如下： Cn=(2n)!((n+1)!n!)C_n = \frac{(2n)!}{((n+1)!n!)}Cn=((n+1)!n!)(2n)!
但是，更常见的是卡特兰数的递推关系： Cn=Cn−1⋅(2n−1)(n+1)C_n = \frac{C_{n-1} \cdot (2n-1)}{(n+1)}Cn=(n+1)Cn−1⋅(2n−1)。
下面我们使用递推的方式来讲解卡特兰数的推导过程。
卡特兰数的递推推导
首先，我们考虑一个简单的场景：如何计算n对括号的合法排列数量。这里，合法排列指的是括号可以正确匹配的排列，例如，对于n=2，合法的排列有()()、(())、()()三种。
基础情况:当n=0时，没有括号，所以只有一个合法排列，即空字符串。因此，C0=1C_0 = 1C0=1。
递推关系:现在，我们考虑如何从n-1对括号的合法排列推导出n对括号的合法排列。
对于任何n对括号的合法排列，第一个括号一定是左括号。在第一个左括号之后，我们可以有以下两种情况：
右括号：这意味着我们关闭了一个括号对，并且剩下的部分是一个n-1对括号的合法排列。
左括号：这意味着我们增加了一个左括号，并且为了保持合法性，后面必须跟着一个右括号。在这两个括号之后，我们有一个n-2对括号的合法排列。
因此，我们可以得出以下递推关系：
如果第一个右括号后面跟着一个n-1对括号的合法排列，那么这样的排列有Cn−1C_{n-1}Cn−1种。
如果第一个左括号后面跟着一个右括号，然后是一个n-2对括号的合法排列，那么这样的排列也有Cn−2C_{n-2}Cn−2种。
由于第一个左括号后面可以跟着一个右括号或者另一个左括号，所以总的排列数量是这两种情况的数量之和：C