递归
递归像俄罗斯套娃:打开一层,里面还有同类的小一层;继续打开,直到没有下一层,才停下。
关键结构图
这一层
打开下一层
继续停下
俄罗斯套娃从大到小排开,箭头表示打开下一层,最后一层停下并返回结果。
What
遇到一个问题,发现里面还有一个类似的小问题,就用同样的方法继续处理,直到不能再往下拆。
递归是一种处理同类嵌套问题的方法。当前这一层会用同一套规则处理下一层,直到遇到可以直接回答的最小情况。
Structure递归 = 同类结构 + 停止条件 + 结果返回
When
当一个东西里面还藏着同类东西时,可以想到递归:文件夹里有文件夹,评论里有楼中楼,任务下面还有子任务。
How
先找到同类结构,再设定停止条件,然后让下一层返回结果。没有停止条件,递归就会一直走下去。
Examples
你要找一个俄罗斯套娃里有没有最小娃娃。打开外面的大娃娃,发现里面还有一个小娃娃,于是继续用同样的方法打开下一层。
你要统计一个文件夹有多少文件。看到子文件夹时,不重新发明方法,而是继续用同样的统计方法处理子文件夹,最后把每层数量加回来。
来源
类型:计算机科学 / 技术文档
事实线:递归通常指函数或过程在解决问题时调用自身,并依赖 base case 停止继续调用。
依据:MDN Web Docs 对 recursion 的编程解释,以及计算机科学中用递归处理树、嵌套结构和可分解子问题的通用教材口径。
边界:递归适合具有同类子结构的问题,但需要明确停止条件和返回结果;在实际程序中还要考虑调用栈、性能和可读性。
常见误读:不要把“重复调用”都叫递归;没有自相似子问题和停止条件,它可能只是循环或无限调用。