️This article has been over 1 years since the last update.

在上一篇的递归中，我们从形而上的角度（数码物）去了解递归，本文从工程角度对递归进行进一步分析。

虽然递归理论上是代码信息密度最高的实现，但是真实拧螺丝中，大部分工作反而是过程式的代码翻译工作，而涉及到递归时一般会有解释器（Curry化）、文件系统或者调度等高级工程问题，因此本文只能介绍应试场景。

应试场景的递归主要难度为代码翻译，代码在定义上很优雅的同时，执行效率上一般是暴力遍历。

大纲

理论

工程纬度分析

在任何一个递归函数中，我们一定只有有限的步骤可以操作，这些是可以枚举的

• 判断：是否为空、比大小（一般需要传递）等
• 操作：只有四种
  • 更深入到子递归；
    • linear recursion
    • tree recursion
  • 停机（比如空）；
  • 有限步骤操作（比如加减计算）；
  • 迭代（但是很少见）；
• 结果：求高度、高度差、总数等，一般会放在递归的Context参数中

关于想象

在上一篇的文章中介绍过，递归是时间的综合，它不是发条式思考，我们不能用递归函数的物理运动轨迹（比如分析调用栈的深度，用笔模拟计算、思考何时回栈、光线追踪等）来代表运动本身，用原子论来描述整体论。递归重点是在定义上，是结构性、声明式为主的状态机定义，而不是过程式编程。

“归纳法”与工程代码的割裂

我们在递归想象上，强调了分而治之的想法，然而在工程上递归始终是从root一侧开始“绕圈”进行遍历的，本质是仍然一个环形的迭代，在DFS一个node一定只会被遍历一次。这就意味着即使你想出了分而治之的思考与递归的定义，物理运动轨迹仍然需要用迭代方案来实现，这种摇摆带来了理解的困难。

这也意味着，你在工程生产中运用的断点分析、函数式计算等积累的经验均难以使用。个人建议是将思考割裂到底，高阶思考时不需要考虑调用栈、前后序遍历等细节，落地时再分析。

Top-down与Bottom-up的思考方式

在真实项目管理中，我们通过拆解Milestone-Storoy-Task来制定任务，这是一种典型的Top-down的思考方式，在递归中也一样， 比如计算Tree的深度，等价于先计算Tree的左与右的最大值。然后编码设计状态机，最终执行。

而Bottom-up的方案，本质是求积分，需要做好时刻的割裂。

应试场景

DFS on binary tree

当我们对Binary Tree的Node进行处理（解释）时，它的属性只有4个，理论上只要逻辑上处理了4个值，就能解决所有的潜在问题。

而所谓的问题，一般是“翻译问题”，和日常拧螺丝的工作并没有本质的区别。值得注意的是，这里一般是用自然语言来描述递归定义（比如 root-to-leaf/inclusive ），你只能用算法/真值表来定义它，难以用亚里士多德的主谓宾的方式来定义。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// dfs伪代码，对上面场景的枚举
// Context是上下文，可以为map/array/StringBuilder等，一般需要“fork”创建
// 可以储存tree的深度/用过的值等
int dfs(Node n, Context c){
  // exit condition
  if(isAtomic(n)){
    // 一般为最下面的叶子/单节点
    atomicHook(n, c);
    return;
  }
  // 一般为根节点和中间节点
  for(child in n.child){
    // 遍历到叶子前的积累操作，主要用于处理AnyMatch
    preHook(n, child, c);
    dfs(child)
    // 从叶子向上回溯，直到有子节点为止，一定需要处理AllMatch
    postHook(n, child, c);
  }
}

这里执行步骤是反直觉的，同时与“分而治之”的想象是割裂的，是按照如下栈的形式执行的

1

pre->pre->...->pre(atomic)->atomic->post(atomic)->...->post->post

这里是最难的思考是postHook，可以用给preHook和postHook染色来进行理解。

这是可能有人就会疑问，这样岂不是变成了死记硬背----当然是这样，for循环加递归这种写法处理时，本质上就是暴力解法，一般会组合爆炸，比较低效，但是高效的算法又是hard的，考起来都完蛋，所以比较尴尬。

さらに、更高阶思考的《递归与偶然》的作者许煜研究递归耗费10年才写出一本书，刷过leetcode只能证明可以借助模版拧螺丝。在这个前提下，DFS问题就简化为了一个如何在一次迭代中实现某个需求，比如求深度、最大值等。

常见DFS问题

求Binary Tree的最大高度：

比如计算“Visible Tree Node”

• Tree的高度：遍历到头时栈的深度
• Tree的三种遍历与反推：建议直接绕过，先了解回溯。
• 记录Tree的path

Backtracking

主要用于排列组合问题（比如n!，必须有序或者独立），这类问题一般会组合爆炸，比较低效，但是高效的算法又是hard的，所以定位上比较尴尬。
常见例子有

• find all root-to-leaf paths
• Combinations/Subsets/Combination Sum
• substring
• 爬楼梯/Decode Ways（约束条件的爬楼梯）

这些问题主要就是暴力循环解决，并适当加一些缓存。

关键控制流

何时判断null

在进行tree的递归时，我们时常会纠结到底用root==null还是root.childs==null，TBD

工程优化

缓存优化

从参数中选一个或者多个参数，返回值可以消费，比如or运算。

DP优化

dp中所用的数组本质上是一种层化的时间维度，用运动轨迹来代替其存在

运行时的栈（选读）

详见动态规划与JenkinsCPS技术

其他

更高的难度问题，比如node多次遍历，依据上下文左右选择等，需要MCTS等方案。