写递归函数的关键在于结构化定义问题：明确黑盒职责（输入、输出、目标），抓住基线条件与分解逻辑，区分分解问题型和遍历探索型思维，并严格控制参数递减与状态回溯。

写递归函数不是“把循环改成调用自己”，而是换一种结构化方式看问题。关键不在语法，而在你如何定义问题、信任子解、并稳住边界。

明确函数的“黑盒职责”

动笔前先一句话说清：这个函数**输入什么、输出什么、整体目标是什么**。不描述过程，只定义契约。

• 比如全排列函数：permute(arr, pos, n) 表示“把 arr 从下标 pos 开始的所有位置，填满所有可能的排列”
• 阶乘函数：fact(n) 就是“返回 n 的阶乘值”，不关心怎么算，只承诺结果正确
• 汉诺塔函数：hanoi(n, src, buf, tar) 意味着“把 n 个盘子从 src 经 buf 移到 tar”，每一步都复用这个语义

抓住两个锚点：基线与分解

递归只有两件事必须讲清楚：什么时候停？怎么把当前问题变成更小的同类问题？其余全是填充。

• 基线条件（Base Case）：最简情形，能直接回答。例如 n=0 或 n=1 时阶乘返回 1；pos == n 时全排列打印结果并返回；n==1 时汉诺塔直接 move
• 分解逻辑（Recursive Step）：用更小规模的调用表达当前任务。例如 fact(n) = n × fact(n−1)；hanoi(n) = hanoi(n−1, src→buf) + move(src→tar) + hanoi(n−1, buf→tar)

区分两种常用思维路径

实际编码中，多数递归可归为两类思路，选对路子事半功倍：

• 分解问题型：函数有返回值，靠组合子问题结果构造答案。典型如斐波那契、阶乘、归并排序——每个调用都在“算一个数”或“返回一个结构”
• 遍历探索型：函数无返回值，专注在递归过程中收集/修改状态。典型如全排列、树的前序遍历、回溯搜索——重点在“走到哪、做什么、回退前清理”

调试与重构的核心习惯

递归容易出错的地方，往往不在逻辑，而在状态管理和边界控制。

• 每次递归调用前，确认参数规模是否严格减小（如 n→n−1，pos→pos+1），否则可能无限递归
• 涉及数组/字符串修改时（如交换元素），务必在递归返回后恢复原状（回溯），否则污染后续分支
• 重构时优先检查基线是否覆盖所有最小情况（比如空输入、单元素、负数等），再验证分解是否自然覆盖所有中间态