全网最全递归算法手写代码 | 看完就会写

▌ 技术引导
递归算法是代码世界里最基础却最容易失控的工具，全网最全递归代码的写法，不是背诵而是理解。我见过太多人写递归代码的时候，连递归的退出条件都糊弄，结果程序直接跑出堆栈溢出。递归的精髓在于：每一步都把大问题拆解成小问题，直到小问题可以解决。
写递归的关键点在于：必须明确base case，必须确保每一步递归都朝着base case靠近，不能无限循环。我之前写一个遍历文件树的递归函数，结果因为读取路径时忘记处理符号链接，导致死循环，最后把硬盘挂满。
现在写递归代码，我习惯在函数开始先处理base case，再处理递归调用，中间用条件判断或者参数flag来控制是否继续递归。另外，递归深度如果超过系统默认限制，必须提前设置setrecursionlimit或者改用迭代方式。
我见过用递归实现广度优先搜索和深度优先搜索的代码，但没几个人真正搞懂为什么用递归而不是迭代。递归代码的结构虽然简单，但要能稳定运行，必须考虑内存和栈溢出的边界。
如果你现在要写一个全网最全的递归代码，别想着复制粘贴，而是要自己手写每一个函数，理解每一个递归步骤的含义，否则你永远不知道哪一步会出问题。

▌ 技术参考

一 递归的本质是一次性把大问题拆解为小问题，但实现时必须确保每一步都有明确的终止条件。比如在写文件遍历函数时，base case是当路径不存在或者不是目录时直接返回。我之前写一个JSON解析函数，就是在这里卡了三次，直到把条件改成if not isinstance(data, dict): return。这个细节在递归函数中至关重要，否则函数可能无限递归下去。

二 实现递归时，函数参数的设计必须包含足够的信息来指导递归的走向。例如在树的遍历中，递归函数需要知道当前节点、父节点以及是否已经访问过。我在写一个分支结构的递归函数时，用了三个参数：current、parent、visited。这不仅帮助我避免重复访问，也让我清楚知道每一步递归的状态。

三 递归函数的调用必须有明确的方向，不能让函数自己决定下一步怎么做。比如在写一个斐波那契数列函数时，必须确保每次调用都是将n拆解为n-1和n-2。我之前写一个排序算法，因为递归函数没有明确拆分思路，导致性能严重下降，甚至出现内存泄漏。后来改用归并排序，把递归拆解为分治法，才解决了问题。

四 Python中递归深度有限制，内置的sys.setrecursionlimit可以调整，但不建议超过10000。我之前用递归写一个解析XML的函数，递归深度达到了3000，结果系统直接报错。后来改成迭代版本，用栈模拟递归过程，不仅避免了错误，还提升了执行效率。

五 递归的性能问题往往体现在栈溢出和重复计算上。比如在写一个计算阶乘的函数时，如果不用记忆化，每次都会重复计算前面的数字。我之前用递归写一个动态规划函数，结果因为没有记忆化，导致时间复杂度飙升，最终用字典缓存结果才解决。

六 在实现多层递归时，必须考虑函数返回值的处理方式。比如一个树的搜索函数，递归函数返回的是布尔值，而递归调用必须将结果传递出来。我在写一个数据库查询递归函数时，就因为没处理返回值，导致整个结果集丢失。后来改用return语句将结果逐层返回，才解决了问题。

七 递归函数的参数传递要谨慎，尤其是值传递和引用传递的差异。比如在写一个修改字符串的递归函数时，每次递归都必须传递新的字符串，否则修改会覆盖原有的数据。我之前写一个字符串反转函数，因为复用了原字符串，导致递归逻辑混乱，最终用切片和拼接的方式重新实现。

八 递归和迭代的性能对比不能一概而论，有些场景递归反而更清晰。比如遍历二叉树，递归代码更简洁，但频繁的函数调用会影响效率。我之前在写一个复杂的编译器解析函数时，发现递归比迭代更易读，虽然系统开销大，但代码可维护性高。

九 递归代码的调试是难点，因为函数调用堆栈复杂。我之前用print语句调试一个递归函数，发现每次调用都输出相同内容，后来用日志记录每个步骤的状态，才找到问题所在。推荐在递归函数中加入log或trace，便于跟踪执行路径。

十 递归函数的线程安全问题常被忽视，尤其是在多线程中使用全局变量时。我之前写一个递归爬虫，因为没有使用线程锁，导致多个线程同时修改同一个变量，出现数据污染。后来改用闭包或者将状态传入函数，才解决了线程安全的问题。

十一 递归的适用场景非常有限，主要用于结构清晰、可以自然拆分的问题。比如图遍历、分治算法、树形结构处理等。我之前用递归写一个动态规划问题，结果因为状态转移不清晰，导致代码难以维护，最后换用迭代方案。

十二 递归的局限性包括栈溢出、性能损耗、调试难度大。比如处理大规模数据时，递归可能因为栈深度不够而崩溃。我在写一个解析大型文件的递归函数时，就遇到了这个问题，后来用栈模拟递归的方式，避免了系统栈的限制。

十三 递归和尾递归的区别在于，尾递归可以被优化成迭代。但Python不支持尾递归优化，因此在写递归函数时，要避免在递归调用后进行额外操作。我之前写一个计算阶乘的尾递归版本，结果Python解释器直接报错，后来改成普通递归，才正常运行。

十四 当递归函数需要处理大量数据时，必须考虑内存占用。比如递归调用时每次都会生成新的栈帧，占用内存资源。我之前用递归写一个深度优先搜索函数，结果内存爆掉，后来改成手动管理栈，用循环代替递归，才解决了内存问题。

十五 在实现递归函数时，可以结合装饰器或工具来增强功能。比如用functools.lru_cache实现记忆化，减少重复计算。我之前用这个方法优化一个递归的组合问题，将时间从数小时缩短到几十秒。