1 · 读书笔记：递归书

The Recursive Book Of Recursion: Ace the Coding Interview with Python and Javascript

https://inventwithpython.com/recursion/ https://book.douban.com/subject/36595842/

• 是什么（What）— 递归是自我引用的问题求解方法，通过基础情况、递归关系、趋向基础情况的进展三要素来解决问题
• 为什么（Why）— 递归天然适合树形和分治问题，代码清晰度高但占栈空间；理解递归=理解函数调用栈的执行过程
• 怎么做（How）— 明确定义三要素、画递归树、考虑栈空间、学习常见模式（线性、二分、多路、回溯）、视需要转迭代

1.1 · 核心观点：

1.1.1 · 1. 递归的本质#

递归是一种自我引用的问题求解方法：

• 定义：函数调用自身来解决较小的子问题
• 三要素：基础情况（base case）、递归情况（recursive case）、趋向基础情况的进展
• 关键认知：递归不是神奇的，它只是用栈展开函数调用

1.1.2 · 2. 递归 vs 迭代#

• 迭代是显式管理状态（循环变量）
• 递归是隐式管理状态（函数调用栈）
• 选择原则：优先选择最能清晰表达问题结构的方式
• 权衡：递归代码可读性强，但会占用栈空间，存在栈溢出风险

1.1.3 · 3. 分治策略（Divide and Conquer）#

• 将大问题分解为小问题
• 递归解决小问题
• 合并子问题的解决方案
• 适用于：树遍历、排序、查找等

1.1.4 · 4. 尾递归优化#

• 尾递归：最后一个操作是递归调用
• 某些语言/编译器可优化尾递归为循环，避免栈溢出
• Python 不支持尾调用优化（TCO）

1.2 · 启发点（关键洞察）：

1. 递归就是栈的可视化：理解函数调用栈是掌握递归的关键。每次调用都会在栈上创建新的帧（frame），这些帧按 LIFO 顺序执行。

2. 基础情况是递归的终点：没有正确定义基础情况，递归会无限进行。基础情况的正确性决定了整个递归算法的正确性。

3. 递归适合树形与分治问题：递归天然适合处理具有树形结构的问题（如树遍历、目录遍历、组合问题），因为递归本身就体现了树的结构。

4. 信任递归的逻辑：在编写递归时，不需要追踪每一层的执行细节，而是信任：如果子问题能被正确解决，整个问题就能被解决。

5. 调试递归需要特殊思维：调试递归时，关注基础情况、递归参数的变化、以及边界条件，而不是手工追踪所有调用栈。

1.3 · 行动：

1. 掌握递归的三要素：在写任何递归前，明确定义：基础情况、递归关系、参数如何趋向基础情况

2. 从简单问题开始：

   • 阶乘（factorial）
   • 斐波那契数列（fibonacci）
   • 二叉树遍历（pre/in/post-order）
   • 简单的列表递归

3. 画出递归树：对复杂的递归，画出调用树，理解每个节点的参数和返回值

4. 考虑栈空间复杂度：计算最大递归深度，评估栈是否会溢出。必要时转换为迭代或使用显式栈

5. 练习常见模式：

   • 线性递归（逐个处理元素）
   • 二分递归（分治问题）
   • 多路递归（组合问题）
   • 回溯递归（搜索、排列组合）

6. 在编码面试中应用：

   • 识别问题的递归结构
   • 快速写出递归解，再优化
   • 能够转换为迭代实现
   • 解释时间和空间复杂度

1.4 · 金句：

1. “递归是一种思考方式，不仅仅是一种编程技巧” — 强调递归的本质是分解问题的思维方式

2. “在递归中，你不需要知道所有的细节，只需要相信递归原理” — 强调信任递归逻辑，避免过度追踪

3. “基础情况是灵魂，没有它，递归就是无限循环” — 突出基础情况的关键重要性

4. “递归不比迭代更慢，但它占用栈空间” — 提醒递归的权衡：清晰性 vs 空间效率

5. “会写递归的人和不会的人的区别，不在于聪慧，而在于练习” — 强调递归是可以通过练习掌握的技能