李煜东 2022-07-27

0x02 递推与递归

状态空间：一个实际问题的各种可能情况构成的集合。

程序的运行是对于状态空间的遍历。

算法和数据结构通过 划分、归纳、提取、抽象 来帮助提高程序遍历状态空间的效率。

递推和递归就是程序遍历状态空间的两种基本方式。

递推与递归的宏观描述

对于一个待求解的问题，当它局限在某处边界、某个小范围或者某种特殊情形下时，其答案往往是一致的。

如果能够将该答案的应用场景扩大到原问题的状态空间，并且扩展过程的每个步骤具有相似性，就可以考虑使用递推或者递归求解。

“原问题”与“问题边界”之间的每个变换步骤具有相似性，这样我们才能够设计一段程序实现这个步骤，将其反复作用于问题之中。

换句话说，程序在每个步骤上应该面对相同类型的问题，这些问题都是原问题的一个子问题，可能仅在规模或者某些限制条件上有所区别，并且能够使用“求解原问题的程序”进行求解。

以已知的 “问题边界” 为起点向 “原问题” 正向推导的拓展方式就是递推。

然而在很多时候，推导的路线难以确定，这时以“原问题”为起点尝试寻找把状态空间缩小到已知的“问题边界”的路线，再通过该路线反向回溯的遍历方式就是递归。

我们可以让程序在每个变换步骤中执行三个操作。

缩小问题状态空间的规模。
这意味着程序尝试寻找在 “原问题” 与 “问题边界” 之间的变换路线，并向正在探索的路线上迈出一步。
尝试求解规模缩小以后的问题，结果可能是成功，也可能是失败。
如果成功，即找到了规模缩小后的问题的答案，那么将答案扩展到当前问题。
如果失败，那么重新回到当前问题，程序可能会继续寻找当前问题的其他变换路线，直至最终确定当前问题无法求解。

在以上三个操作中有两点颇为关键。

“如何尝试求解规模缩小以后的问题”。因为规模缩小以后的问题是原问题的一个子问题，所以我们可以把它视为一个新的“原问题”由相同的程序进行求解，这就是所谓的“自身调用自身”。
如果求解子问题失败，程序需要重新回到当前问题去寻找其他的变换路线，因此把当前问题缩小为子问题时所做的对当前问题状态产生影响的事情应该全部失效，这就是所谓的“回溯时还原现场”。

递归程序的基本单元是由 “缩小” “求解” “扩展” 组成的一种变换步骤，只是在 “求解” 时因为问题的相似性，不断重复使用了这样一种变换步骤，直至在已知的问题边界上直接确定答案。

对于其中任意一条从 “原问题” 到 “问题边界” 的变换路线，横向来看，它的每一层是一次递归程序体的执行；纵向来看，它的左右两边分别是寻找路线和沿其推导的流程。

为了保证每层的 “缩小” 与 “扩展” 能够衔接在同一形式的问题上，“求解” 操作自然要保证在执行前后程序面对问题的状态是相同的，这也就是 “还原现场” 的必要性所在。