1. 核心抽象

递归不一定要从 Subproblem 出发。更一般的理解是 State Space + Transition + Computation。

定义：

  • State \(s\)：当前计算状态，属于状态空间 \(S\)。
  • Transition \(T(s)\)：从状态 \(s\) 可到达的后继状态。
  • Result \(R(s)\)：状态 \(s\) 对应的计算结果。
  • Aggregation \(F\)：如何利用后继状态的结果计算当前结果。

对于无环依赖结构，典型的递归关系是：

\[ R(s)=F\left(s,\bigl(R(t)\bigr)_{t\in T(s)}\right) \]

DFS 可以看作对这个依赖关系进行求值的一种方式。

2. 递归中的两种信息流

Result dfs(State s, Context ctx)

  • Top-down（向下传递）：父节点通过参数向子节点传递 Context，例如 depth、pathSum、remainingTarget。
  • Bottom-up（向上返回）：子节点通过返回值向父节点提供 Result，例如 height、subtreeSize、maxPath。

两者可以同时存在。

设计时先问：

  1. 当前状态需要哪些来自祖先的信息？
  2. 当前状态需要哪些来自后继状态的结果？
  3. 返回什么信息，才能让调用者继续计算？
  4. Base case 应该返回什么？

3. DAG：Pull vs. Push

比 Top-down / Bottom-up 更一般的区分是：

Pull：从依赖节点读取信息

\[ R(v)=\operatorname{Aggregate}_{u\in T(v)}R(u) \]

例如 DAG 中，从 \(v\) 到终点的路径数量：

\[ R(v)=\sum_{v\to u}R(u),\qquad R(\text{target})=1 \]

可以使用 DFS + Memoization。

Push：沿状态转移传播信息

\[ R(u)\leftarrow R(u)\oplus G(R(v),v,u) \]

例如从起点到各节点的路径数量，可以按照拓扑序传播。

注意：

  • 状态转移方向 ≠ 结果依赖方向 ≠ 函数调用顺序。
  • Top-down / Bottom-up DP 也常用来区分 memoization 和迭代 tabulation，不应混淆。

4. State 的充分性

State 必须包含决定后续计算所需的全部信息。

例如 dfs(v, pathSum) 中，如果结果依赖 pathSum，那么完整状态是 (v, pathSum)，不能只根据 v 做 memoization。

好的状态设计要求：

  • Sufficient：信息充分，不会错误合并不同状态。
  • Minimal：尽可能消除冗余，避免状态空间爆炸。

5. 与编程范式的关系

  • Functional Programming：计算是从 State 到 Result 的函数映射。
  • Dataflow Programming：关注信息依赖、传播与聚合。
  • State-machine Modeling：关注状态空间和状态转移。
  • DFS / DP：在这些结构上实现计算的不同策略。
Key takeaway

核心思想：先定义 State、Transition、Dependency 和 Result，再选择 DFS、DP、拓扑排序或其他算法来执行计算。

递归是一种执行机制，而状态与依赖关系才是算法设计的基础。