%%
# 纲要
> 主干纲要、Hint/线索/路标
# Q&A
#### 已明确
#### 待明确
> 当下仍存有的疑惑
**❓<font color="#c0504d"> 有什么问题？</font>**
# Buffer
## 闪念
> sudden idea
## 候选资料
> Read it later
%%
# 分治法
分治法：将原问题划分成若干个**规模较小**而**结构、形式与原问题相同或相似的子问题**（**==分==**），通过**递归**求解这些子问题（**治**），而后**合并子问题的解，得到原问题的解**（**==合==**）。
根据分解出的子问题的规模，分治法可细分为：
- **==减治==**（Decrease and Counquer）：拆分出的其中一个子问题**规模为 1**，其余子问题**规模缩减**
- **==分治==**（Divide and Conquer）：拆分出多个**规模相当**的子问题
<br>
### 分治法的应用前提
分治（包括**减而治之**和**分而治之**）是一种分析、求解问题的思路，但并非所有问题都能通过该思路解决。
- 有的问题**只能采用其中一种方式**（例如**反转数组**，只能**减治**）
- 有的问题既可以采用 **减治**，也可以采用**分治**（例如数组求和）
- 有的问题在递归过程中根据具体情况的变化，时而为"**减治**"，时而为"**分治**"（例如最长公共子序列）
能采用分治的前提是：**原问题可以拆分为规模更小的、与原问题形式相同的子问题求解，在得到子问题的答案后即可确定原问题的答案**。
如果不满足这一点，就不能应用分治求解。
> [!example] 例如，**括号匹配问题，不能用分治解决**。
>
> 如上图所示，**原问题中的括号表达式是合法的**，但将原问题拆为规模更小的子问题后，**子问题的括号表达式非法**。
> **故无法由子问题推出原问题的解**，所以不能应用分治。
>
> 
>
<br><br>
## 减而治之 Decrease and Conquer
**减而治之**：大规模问题拆分为**两个子问题**：
- 其一是退化的**平凡问题**，即**规模为 1 的情况**，能够以较优的时间复杂度直接求解
- 其二是**规模缩减的问题**，其与原问题形式几乎一样。
**递归**地求解出问题的解，再不断地将**问题的解合并起来，得到原始问题的解**。
### 递归形式
减而治之对应的递归形式：「**==线性递归==**」，每次缩小一个单位。**递归深度通常近似为 $n$**，即原问题的规模数。
- 如果求解规模为 1 的子问题只需要 $O(1)$，则求解原问题的复杂度即为 $O(n)$。
- 如果求解规模为 1 的子问题需要 $O(\log n)$，则求解原问题的复杂度为 $O(n\log n)$。
> [!NOTE] **线性递归**的过程示意：
>
> 
>
>
### 示例场景
可通过 "减而治之" 的思路递归求解的题目：
- 反转链表、翻转数组、数组求和
- **插入排序**
- 通常是以迭代实现，但也可以从"减而治之"的角度去看待，以递归的方式实现：
将前面段排序好，再将末尾元素插入到其中正确的位置。递归深度是 n，每次找到正确位置并插入的时间复杂度也是 n，所以最终时间复杂度为 `O(n^2)`。
<br><br>
## 分而治之 Divide and Conquer
分而治之，将大规模问题拆分为**若干个子问题**（通常两个），**各个子问题规模大体相当**，且子问题与原问题形式几乎一样。
**递归求解子问题**，由子问题的解合并得到原问题的解。
### 递归形式
分治思路对应的递归形式：「**==树形递归==**」，每次**拆分为两个或多个规模相当的子问题**（即分裂为两个或多个子调用）
- 拆分出来的**两个子问题的总规模之和可能大于原问题**，例如约为原问题的两倍
（例如最长公共子序列）
- **每层递归调用**的次数**呈"==几何数列=="的形式增长**，时间复杂度取决于**递归深度**；
- 假设每次拆分为两个规模相当的子问题，且**合并子问题的开销**是 $O(1)$ ：
- 若递归深度为 $\log n$，则时间复杂度为 $O(n)$； （$2^{\large \log n}=n$）
- 若递归深度为 $n$，则总时间复杂度为 $O(2^n)$ 。
> [!note] **树形递归**的递归过程示意：
>
> 
>
### 示例场景
可通过"分而治之"的思路递归求解的题目：
- 数组求和
- 斐波拉契数列
- 最长公共子序列
---
<br><br>
# 递归
递归：指**函数内部调用自身**的编程技巧。
> [!NOTE] **减而治之、分而治之**是"思想"，是分析与解决问题的思路，而**递归是对二者的==实现方式==**。
递归的核心概念：
- "**==递归基==**（Base Case 或 Base Condition），也称**递归边界**、基准条件、递归出口
- **递归的终止条件**，防止无限递归。
- "**==递归式==**"（Recursive Case），也称递归关系
- 将原问题拆分为若干子问题的过程，如 `F(n)=F(n-1)*n`，
## 递归的优化思路
"减而治之"，"分而治之"都是从 "**自顶向下**" 的角度去求解，
**如果**在递归的过程中可能存在 **大量重复的递归实例**（重复计算），两种优化思路是：
- **==记忆化搜索==**（备忘录）/ tabulation / memoization：
- 仍然从原问题出发自顶向下，每当遇到一个子问题就**查表看是否已经计算过**，每个子问题首次计算后都将结果记入表中。
- **动态规划** / Dynamic Programming：
- 从**递归基出发**，**自底向上**地**递推**得到最终答案的解。
## 尾递归
尾递归（Tail Recursion）是一种特殊形式的递归。
在这种递归中，**==递归调用==是函数的最后一个动作**，即**函数返回的是直接结果 or 对自己的递归调用**。
这一特性使得 **尾递归可以被编译器优化**：
- **栈帧重用**：
- 由于当前函数返回的结果就是**递归调用的结果**，故**当前函数的执行上下文（比如局部变量、参数等）不再需要保留**，于是编译器可以 **==重用相同的栈帧来执行递归调用==**，而不是在每次递归时创建新的栈帧。这就意味着无论递归多深，**整个递归过程==只占用一个栈帧的空间==**，可以显著减少内存的使用，甚至**避免栈溢出**。
- **转换为迭代**：
- 基于栈帧重用，尾递归的性质使得编译器**可以将其转换为迭代的形式**。在这种转换中，**原来的递归调用被替换为一个循环**，而原来的**函数参数则通过循环的迭代来更新**。
> [!NOTE] **尾递归形式的代码在==逻辑上==一定能够被改写成 ==迭代循环形式== 的代码**
> [!caution] 注：并非所有编程语言的编译器都自动进行尾递归优化。
>
> - C/C++ ：**尾递归优化的发生依赖于编译器的具体实现和优化设置**。
> - Java：Java 虚拟机（JVM）通常不进行尾递归优化，
> - Haskel、Scheme 等函数式编程语言：将尾递归优化作为语言规范的一部分。
>
<br>
### 尾递归与非尾递归的区别
尾递归与非尾递归的**主要区别在于==递归调用后==是否还有其他操作**。
如果函数在递归调用后不执行任何操作（即直接返回递归调用的结果），则该递归是尾递归。
示例一：计算 n 的阶乘
```cpp
// 计算阶乘
// 非尾递归版本
int factorial(int n) {
if (n == 0) return 1;
return n * fractorial(n - 1); // 非尾递归, 递归调用后还有乘法操作.
}
// 尾递归版本
int factorial(int n, int accumulator = 1) {
if (n == 0) return accumulator;
return factorial(n - 1, accumulator * n); // 尾递归, 递归调用是最后的操作
}
```
示例二：计算斐波那契数列的第 n 项（`F(0)==0`, `F(1)==1`）。
```cpp
// 非尾递归版本
int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2); // 非尾递归, 两路递归调用, 而且还要相加
}
// 尾递归版本
// 初始时a==0即F(0), b==1即F(1).
// 每次递归时b更新为前两个斐波拉契数a+b的和, 而a更新为b.
// 从2开始, 要得到第n个斐波拉契数, 需要再迭代n-1次, 因此递归调用为`n-1`.
// 递归到第n-1次时, n为1, 此时返回的b即为结果.
int fibonacci(int n, int a = 0, int b = 1) {
if (n == 0) return a;
if (n == 1) return b;
return fibonacci(n - 1, b, a + b); // 尾递归;
}
// 迭代版本(尾递归的逻辑即对应着迭代的逻辑)
int fibonacci(int n) {
if (n < 2) return n;
int a = 0, b = 1;
for (int i = 2; i <= n; ++i) {
int tmp = a + b;
a = b;
b = tmp;
}
return b;
}
// 等价的迭代
int fibonacci(int n) {
if (n < 2) return n;
int a = 0, b = 1;
--n;
while (n--) {
b += a;
a = b - a;
}
return b;
}
```
<br><br>
# 记忆化搜索（自顶向下）
**记忆化搜索**（也称 "**记忆化递归**" 或 "**备忘录法**"）。
「记忆化搜索」是从**顶层问题**开始，**自顶向下地通过==递归==求解子问题**，并在**每次递归调用时检查和存储子问题的中间结果**。
> [!note] 「记忆化搜索」本质上即 "**==分治==（递归实现） + ==备忘录==**" ^zoo8sz
##### 主要思想
1. 将递归过程中遇到的**子问题的解**进行记录（例如**记录在数组或哈希表**中）
2. 每当**递归调用**需要解决一个子问题时，首先**检查这个子问题是否已经解决过**：
- 如果**已解决过**，则**直接使用存储的结果**；
- 如果未解决过，则**计算该子问题的解**，并将其 **==存储==起来**以备后用
<br><br>
# 参考资料
# Footnotes