一、尾递归上一篇对递归进行了一些讨论但学习递归不是通过一次阅读或者一次编码就能学会的。需要进行一定量的练习巩固最终还是落在遇到问题即能规划递归函数上。上一篇的递归形式定义的阶乘一例代码大概长这样int Jc(int x){ if(x1){ //边界1!1 return 1; }else{ //x!x*(x-1)! return x*Jc(x-1); } }我们回顾一下上一篇的描述中有这样一段内容C调用函数时会维护一个栈结构——保存当前数据状态——寄存器调用完还会恢复以确保调用不混乱。实际上这段描述为了简化认知过程表述是不正确的。真正的过程是这样的维护调用栈Call Stack是“硬件CPU 操作系统ABI 编译器代码生成”三方协同的结果连接器Linker基本不参与。C 语言本身标准库完全不维护栈它只是栈的“使用者”。当你写void foo(){ int a; bar(); }实际过程应该是这样的编译时编译器决定a放在RBP-4决定调用bar前压参方式生成对应的push/pop汇编。链接时连接器把foo的机器码放到最终文件的.text段不做任何栈维护逻辑。运行时CPU执行call压返回地址执行push压局部变量。异常时OS 编译器表如果bar抛出异常操作系统读取.eh_frame表找到foo的栈顶位置进行栈展开Stack Unwinding。维护调用栈的“动作”指令由编译器生成“执行”由 CPU 完成“内存”由操作系统提供“连接器”只负责把东西打包C 语言本身对此一无所知。回到尾递归我们不管是谁维护了这个栈是谁在使用这种调用一定会消耗一些CPU算力——无论是搬运数据还是其他操作都可能影响程序效率所以很多时候递归函数表现得比相同功能的循环要慢。但有一个特殊情况当递归调用的结果直接被return时。这时保存当前寄存器等状态是无意义的例如在32位时代通常使用EAX来返回值、64位中通常使用RAX我们不做更深的数据类型和操作系统差异讨论我们只需要按调用过程把返回值一直放在那里就可以了。所以无需进行压栈和弹栈那套动作递归的表现就要好很多。这种情况就称为尾递归尾递归性能比其他位置递归好很多和循环相差无几。二、回溯、记忆化搜索的有效边界在使用递归的时很难避开回溯这个话题尤其在竞赛方向。有一部分人在学习很久之后都搞不清楚要不要回溯实际上这个事情非常非常的简单如果当前for中的递归调用之间是合作完成最终目标那么无需回溯如果当前for中的递归调用之间是独立的各自都需要完成目标那么必须回溯。举例进行简单说明1、用递归写快速种子填充算法那么for 4个方向上是合作的——填完满足条件的区域2、用递归写马遍历棋盘有多少方案那么for 8个方向上是独立地、并行的——每个都需要独立完成遍历任务。从算法逻辑的拓扑结构来说这是区分分治/Flood Fill类型的递归和回溯/DFS计数型递归最本质的数学特征。1、合作并集OR/只要一个成功)代表算法种子填充、连通区域标记……当前for的逻辑关系涂完上且下且左且右最终目标达成2、独立笛卡尔积OR/多种可能性代表算法马走日、N皇后、全排列、路径计数……逻辑关系方案总数方向1的方案总数方向2的方案总数……3、记忆化搜索的边界合作模式较难并行计算记忆化也无效独立模式天然适合并行计算记忆化搜索极其有效。关于并行计算之类的更繁杂的问题不在这篇的讨论范围之内。三、稍微专业点递归中子问题的耦合度决定了调度的本质1、在合作中递归树是以来共享变量的深度优先遍历子问题间存在读写冲突因此必须同步协作。2、在独立中递归树是搜索空间的深度优先枚举子问题间不存在数据竞争每个分支都是独立完成的计算任务最终结果知识分支结果的可交换累加。实际上顶层的数学逻辑拓扑任务和底层的物理机制栈还是有强对应关系的这里就不做更深讨论了。“合作”是为了物理世界的累积涂色面积“独立”是为了逻辑世界的计数方案数量。前者追求的是“改变世界”后者追求的是“遍历世界”。区分好它们就可以区分好用不用回溯。当然我们也可以换个角度从更代码的角度用什么来记录的当前状态来考虑问题当前状态能否建立在兄弟递归的结果基础上如果不能那就需要把当前状态恢复到for之前——父状态——即回溯。这样讲可能更有利于一部分人理解状态记录数组、是否回溯、如何实现之间的关系。