标签：递归

CSPJ 教学总结：深度优先搜索（DFS）

深度优先搜索（DFS）是算法学习的基础，其核心是递归实现，需通过参数传递保存搜索状态。标准DFS模版包含终止条件、合法选项枚举、状态标记与恢复等关键步骤。实际应用中需关注递归深度对栈空间的占用，竞赛环境通常限制栈大小为8-16MB，建议递归深度控制在1万层以内以防溢出。 通过多类典型题目可深入理解DFS应用：八皇后问题通过逐行放置并检查斜线冲突实现经典搜索；选数问题采用递归枚举组合并判断素数；Lake Counting与迷宫问题利用DFS进行连通区域标记与路径探索；PERKET问题通过DFS枚举所有选菜组合计算酸度甜度差；黑白棋问题需结合多重剪枝策略（行列计数、连续检查、唯一性验证）优化搜索；自然数拆分问题则通过保证数列非递减来避免重复解。这些案例展示了DFS在组合枚举、图遍历、约束满足等场景中的灵活应用，体现了状态保存、剪枝优化等关键思想。

算法模式：子集

在2048里能够得到的最大的数是多少？

这篇讲的是2048游戏的一个数学极限问题。作者从Michael Brand的一个谜题出发，探讨了在这个著名的合并数字游戏中，理论上能得到的最大数字究竟是多少。 文章首先简明地解释了游戏规则，然后切入核心证明：为什么2¹⁸ (262144) 这个数字在4×4的棋盘上永远无法得到。作者通过一个巧妙的二进制分析指出，棋盘上所有数的总和的二进制表示中，“1”的个数不可能超过棋盘格子数16。而要产生一个2¹⁸，其总和的前一步必然是一个二进制“1”个数达到16的状态，这意味着棋盘恰好被2²到2¹⁷这16个不同数字块完全填满，无任何合并空间，游戏直接结束。 由此，131072 (2¹⁷) 成为理论上限。但作者进一步指出，这个数字本身能否达成仍是一个开放问题。尽管有玩家声称成功，但缺乏完整演示过程。文章留下了两种可能性：要么找到一种确定的构造方法来达成131072，要么给出一个更严密的证明来否定它。这使得一个看似简单的游戏，引向了一个关于数学构造与边界的有趣思考。

为什么Fibonacci数列相邻两项之比会趋于0.618？

这篇文章从斐波那契数列相邻两项的比值现象出发，解释了它为何会趋近黄金比例0.618。作者没有停留在代数推导上，而是借助 Mathematica 动画，通过“黄金矩形”的几何构造给出了一个直观而优美的解释。 核心思路是：以斐波那契数对（1,1）、（1,2）、（2,3）…为边长构造矩形序列，每个新矩形都由前一个旋转90度并拼接一个正方形生成。随着图形不断递归生长，初始细节的影响逐渐消散，矩形整体与其内部的小矩形变得高度相似——这正是黄金矩形的定义特征。图形化演示清晰地展现了，无论起始矩形的比例如何，最终都会收敛到相同的黄金比例。 文章还顺带点明了一个有趣的结论：任何遵循“每项为前两项之和”规律的数列（哪怕起始值是任意的2和7），其相邻项比值最终都会收敛到0.618。这让抽象的数学规律变得可看、可感，也解释了一个常见的数学魔术背后的原理。

尾递归对时间与空间复杂度的影响

这篇讲的是尾递归在实际应用中那些理论之外的复杂性。文章从一位同学的提问出发：是否所有递归算法都能改写为尾递归？改写后，时间和空间复杂度就一定能得到优化吗？以斐波那契数列为例，表面上似乎验证了这一结论。 作者深入剖析后发现，事情并非如此简单。虽然尾递归确实能通过消除调用栈来优化空间复杂度，但其对时间复杂度的提升是有条件的。文章具体展示了，即使将斐波那契递归改写为尾递归形式（借助累加器参数），若仅仅进行机械转换，得到的依然是一个时间复杂度为 O(2^n) 的低效算法，需要进一步结合动态规划思想才能优化到 O(n)。 文章进而探讨了将一般递归转换为尾递归或迭代的通用方法，分析了转换过程中可能遇到的困难与权衡。结论是，尾递归是一个强大的性能优化工具，但它不是将递归问题转化为高效迭代代码的“万能钥匙”。理解其原理与局限，才能在合适的场景下有效运用它。

小心递归次数限制

这篇讲的是作者从一次真实的代码审查经历出发，揭示了Python代码中一个容易被忽视的“陷阱”：默认的递归深度限制。 他发现的递归调用本身逻辑似乎没问题，但在测试数据量增大时，程序会突然崩溃，抛出“Maximum recursion depth exceeded”错误。问题的根因在于，Python解释器为了防止栈溢出，对递归深度设置了默认限制。当递归层次过深时，这个限制就会被触发。作者不仅指出了问题，更深入地探讨了如何在工程实践中应对它：是通过“sys.setrecursionlimit”临时提高限制，还是将递归算法重构为更稳定的迭代或循环形式？文章强调，解决方式的选择取决于具体场景，但更重要的是，这种潜在的失效点需要在代码设计初期就被预见和评估。这个案例提醒开发者，对于递归这类“强大但需谨慎”的工具，保持一份必要的警惕，并在关键逻辑中做好防御性设计。

程序设计中的计算复用(Computational Reuse)

这篇讲的是计算复用——一个通过“记住结果”来避免重复劳动的编程思想。作者从斐波那契数列这个经典例子切入，直观对比了三种计算方式：朴素递归的指数级时间复杂度，记忆化（Memoization）的显著提速，以及动态规划（Dynamic Programming）的自底向上最优解。 文章的核心并非仅仅讲解算法，而是以它为透镜，阐释“计算复用”这一更通用的模式。它清晰地指出，在计算资源有限的现实世界中，单纯追求代码的优雅或直观是不够的，我们必须有意识地在“用空间换时间”和“设计更优的计算路径”之间做出权衡。这种思想不仅适用于算法竞赛，更是优化任何有大量重复计算场景（如前端渲染、数据库查询）的关键。 最后，文章将计算复用与“抽象”和“设计模式”进行了有启发的类比。它告诉我们，优秀的程序员不仅是在写代码，更是在设计一个高效、可复用的“计算过程”。这种从具体代码上升到通用思想的视角，能帮助我们在面对复杂系统时，更主动地去寻找和设计其中的复用机会。

递归字符转义

这篇分享的是ecshop电商平台源码中一个用于字符转义的递归函数。作者从实际代码出发，拆解了这个函数如何解决一个常见但容易被忽略的问题：当数据以复杂嵌套数组或对象的形式传入时，如何确保内部所有字符串值都被统一、安全地转义处理。 函数的巧妙之处在于其递归设计。它并非简单地遍历一层键值对，而是能够深入检测每个值的类型——如果是字符串则执行转义操作；如果是数组或对象，则自动将自身作为工具递归调用，从而“钻入”数据结构的每一层。这避免了开发者手动编写多层循环来处理不规则数据的麻烦，保证了无论数据结构嵌套多深，转义都能彻底执行。 在安全处理用户提交的数据、防止SQL注入或XSS攻击的场景下，这种通用性强的递归方案显得尤为实用。作者通过分享这个细节，展示了如何用递归思维优雅地解决实际工程中的防御性编程需求。

递归创建目录的一个函数

这篇讲的是从OpenID的PHP源码中提取的一个递归创建目录函数，作者认为它简洁高效，很值得开发者参考。在实际开发中，动态创建多级目录是常见需求，比如处理用户上传或生成临时文件时，传统方式可能需要循环或手动检查，容易出错。这个函数采用递归思路，通过调用自身逐级创建父目录，即使目标路径的中间层级不存在，也能自动补全。 核心实现上，它先判断目录是否已存在，若不存在则递归处理上级目录，再创建当前目录，并加入了错误处理以确保鲁棒性。巧妙之处在于代码仅用几行就完成了复杂逻辑，既避免了冗余代码，又保持了良好的可读性。这种递归方法比迭代更优雅，减少了手动维护的麻烦。 在实际项目中应用这样的函数，能快速集成目录生成功能，提升代码的简洁度和可靠性。作者通过分享这个实例，展示了如何从现有代码库中提炼实用工具，为类似场景提供了一种干净利落的解决方案。

倒置字符串中的单词

这篇讲的是一个经典字符串处理问题——如何高效地倒置句子中的单词顺序，比如将“Hello World”转换为“World Hello”。作者从编程面试和日常数据清洗场景切入，深入剖析了两种核心实现方案：基于栈的临时存储法和利用双指针的原地反转法。 栈方案通过遍历字符串将单词压栈再弹出，逻辑直观，但需要O(n)的额外空间；而双指针法则通过先整体反转整个字符串，再逐个反转每个单词的方式，实现了原地操作，将空间复杂度优化至O(1)。文章特别强调了双指针法中的巧妙之处：如何在反转过程中准确识别单词边界

看来看去都是看数学书

这篇讲的是计算机领域一个有趣的现象：数学门槛似乎在程序员毫无准备时突然升高。作者以函数式编程和形式化验证两个领域为例，生动描述了技术发展如何带来意料之外的数学挑战——当大家刚适应用类似LOGO的LISP写代码时，monad和范畴论突然成了必修课；而做模型检测的工程师，本以为只需处理逻辑和状态空间，却可能被拓扑与同伦理论的文献绊住脚步。 文章用略带调侃的笔触，揭示了一个深层趋势：现代计算机科学的某些分支正在吸收更抽象的数学工具。这并非故作高深，而是问题复杂度提升的自然结果。作者通过具体案例（如范畴论需多年抽象训练、同伦理论的专业性）暗示，这种“数学跃迁”可能让非科班出身的开发者感到困惑甚至劝退。 文中流露的核心观察是：技术进步有时会悄悄抬高某个领域的认知基线。这对从业者的启示或许在于，保持对基础数学的敬畏与持续学习的能力，或许比掌握某种流行语言更为持久。

算法复杂度求法初学

这篇讲的是如何为算法复杂度分析打下第一块基石。作者从最基础的概念出发，手把手拆解了“时间复杂度”与“空间复杂度”这两个核心度量维度。文章没有堆砌高深的公式，而是紧扣“初学”二字，清晰地阐述了大O表示法的由来与核心原则，比如如何忽略常数项、只保留最高阶项。 最关键的是，作者结合具体的代码片段（如简单的循环与嵌套循环），演示了如何一步步推导其复杂度。这种从具体代码到抽象表示的过程，正是初学者最需要跨越的台阶。文中还辨析了最好、平均与最坏情况复杂度的区别，让读者明白算法性能评估的实际语境。 整篇文章的讲解节奏平缓而扎实，就像一位耐心的前辈，在白板前带你画出算法效率分析的第一条曲线。对于刚接触数据结构与算法、却对复杂度概念感到模糊的开发者来说，它提供了一个清晰且可操作的入门路径。