递归基础：从函数调用到递归树

很多人第一次接触递归时，会有一种很强烈的“不踏实感”。明明平时写函数都是从上往下顺着执行，可一到了递归，函数居然在自己调用自己，看起来像是会无限套下去。尤其是第一次看到树的遍历、分治、回溯这些题目时，递归常常像一扇门：看懂了会觉得思路非常自然，看不懂就会觉得整件事很玄。

但递归其实并不神秘。它不是某种脱离普通程序执行逻辑的特殊技巧，而只是把“大问题”拆成“更小但结构相同的问题”，再交给同一个函数去处理。你可以把它理解成一种非常强的表达方式：当问题本身就带有层级、重复、自相似结构时，递归往往能把代码写得更直接，也更贴近问题本质。

在数据结构里，递归几乎无处不在。树的定义天然递归，二叉树遍历天然递归，归并排序、快速排序、二分查找、图的深度优先遍历，也都离不开递归思想。所以在正式进入树、图和更复杂结构之前，先把递归的基本逻辑吃透，会让后面很多内容顺很多。

一、为什么要先学递归

很多初学者会把递归当成“一个写法”，觉得它只是循环之外的另一种实现方式。这个理解不算错，但还不够深。

递归真正重要的地方在于：

它训练你把问题不断拆小；
它训练你从“整体定义”反推“局部关系”；
它帮助你更自然地理解树、分治、回溯和很多算法流程；
它让你开始真正理解函数调用栈是怎么工作的。

也就是说，学递归不只是为了会写几道题，而是为了建立一种新的思考方式：

如果一个问题和它的子问题长得一样，那我能不能先解决子问题，再把结果拼回来？

这种思路，在数据结构和算法里非常常见。

二、什么是递归

递归可以先用一句非常朴素的话来理解：

函数在定义过程中调用自己，去解决规模更小的同类问题。

这里有两个关键词特别重要。

1. 同类问题

不是任何问题都适合递归。只有当“大问题”和“小问题本质上是同一种结构”时，递归才自然。

例如：

计算 n!，本质上可以写成 n * (n-1)!；
计算斐波那契数列，第 n 项可以由前两项表示；
遍历一棵树时，一棵树的左子树和右子树本身又都是树；
归并排序中，排序整个数组可以拆成排序左半部分和右半部分。

2. 规模更小

递归不是“无脑自己调自己”，而是每次调用都必须向更小的规模推进。只有这样，问题才会一步步逼近终止条件。

所以递归最核心的结构通常包含两部分：

终止条件；
递归关系。

没有终止条件，递归就会无限下去；没有递归关系，递归又无法把大问题拆开。

三、先从一个最简单的例子开始：阶乘

比如 5!：

1	5! = 5 × 4 × 3 × 2 × 1

如果换一种写法：

1	n! = n × (n - 1)!

而当 n = 1 时：

1! = 1

这就已经是一个完整的递归定义了。

用 Python 写出来大概是这样：

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

这里：

if n == 1 是终止条件；
n * factorial(n - 1) 是递归关系；
每次调用都把问题从 n 变成 n - 1，规模在缩小。

如果你把 factorial(5) 的展开过程写出来，会看到：

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1

这就是递归最基本的运行直觉。

四、递归函数到底是怎么执行的

很多人学递归时真正卡住的，不是公式看不懂，而是不清楚程序执行时到底发生了什么。

要理解这一点，必须先知道：

每次函数调用，都会在调用栈里创建一个新的栈帧，用来保存这次调用的局部变量、参数和返回位置。

也就是说，递归并不是“一个函数神奇地同时做很多事”，而是：

第一次调用先暂停在某个位置；
再进入下一层更小的调用；
再继续进入更小的一层；
直到碰到终止条件；
然后再一层层返回，把结果带回去。

还是以 factorial(4) 为例，它的执行大致像这样：

factorial(4)
→ 等待 4 * factorial(3)
→ factorial(3) 等待 3 * factorial(2)
→ factorial(2) 等待 2 * factorial(1)
→ factorial(1) 返回 1
→ factorial(2) 返回 2 * 1 = 2
→ factorial(3) 返回 3 * 2 = 6
→ factorial(4) 返回 4 * 6 = 24

你会发现，递归调用时“往下走”是在不断拆问题，“往上返回”才是在逐层组装答案。

五、递归最核心的三件事

写递归时，最重要的不是一开始就想清楚每一步怎么跑，而是先抓住这三个问题。

1. 这个函数的定义是什么

也就是：

这个函数到底负责解决什么问题？

例如：

factorial(n) 表示“返回 n 的阶乘”；
dfs(node) 表示“遍历以 node 为根的整棵子树”；
binary_search(arr, left, right, target) 表示“在指定区间里查找目标值”。

函数定义越清晰，递归越容易写。

2. 终止条件是什么

任何递归都必须有一个能直接返回结果的最小情况。

例如：

阶乘里 n == 1；
遍历链表时 node is None；
遍历树时根节点为空；
二分查找里区间已经无效。

终止条件本质上是在回答：

问题缩小到什么程度时，我可以不再继续拆，直接给答案？

3. 递归关系是什么

也就是：

当前问题如何通过更小的子问题来表示？

例如：

阶乘：n! = n × (n-1)!
斐波那契：f(n) = f(n-1) + f(n-2)
二叉树高度：height(root) = max(height(left), height(right)) + 1

很多递归题其实只是在反复训练这件事：把原问题翻译成“当前层怎么利用子问题结果”。

六、递归为什么特别适合树结构

树是递归最典型、也最自然的应用场景。

原因非常简单：

一棵树的子树，本身还是树。

这意味着很多树的问题天然就满足“整体和子问题同构”的条件。

例如二叉树前序遍历：

访问根节点；
前序遍历左子树；
前序遍历右子树。

这件事写成递归就特别自然：

def preorder(root):
    if root is None:
        return
    print(root.val)
    preorder(root.left)
    preorder(root.right)

之所以看起来这么顺，是因为代码几乎直接复述了问题定义本身。

这也是递归最强大的地方之一：

当问题本来就带有层级结构时；
递归往往能把“定义”直接变成“代码”。

所以后面你学树的遍历、树高、节点计数、路径和等问题时，会越来越频繁感受到递归的自然性。

七、什么是递归树

当递归调用层次比较复杂时，只靠脑子跟踪会很累，这时就很适合引入“递归树”的视角。

递归树可以理解成：

把一次递归过程展开成一棵调用关系树，看每一层做了多少工作、总共有多少层。

比如斐波那契递归：

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

如果展开 fib(5)，会形成很多重复子调用：

fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

这棵调用树会帮你很直观地看到两个事实：

同一个子问题被重复计算了很多次；
递归不一定都高效，关键要看调用结构。

所以递归树不仅帮助理解执行过程，也帮助分析复杂度，尤其是在分治和递推关系问题里非常有用。

八、递归和循环是什么关系

很多时候，递归和循环都能解决问题，所以初学者常会问：

既然循环也能做，为什么还要学递归？

更准确的答案是：两者很多情况下可以互相转换，但表达重点不同。

1. 循环更适合线性、重复、状态简单的问题

例如：

遍历数组；
顺序累加；
固定次数重复操作。

2. 递归更适合层级、自相似、拆分式问题

例如：

树遍历；
分治排序；
回溯搜索；
图的深度优先遍历。

不是说递归一定更高级，而是它在某些问题上表达得更直接。

例如计算阶乘，用循环也完全可以：

def factorial(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

这时递归和循环都行，但如果问题天然是一棵树、一层层嵌套结构，递归通常会更贴近定义。

九、递归最容易出现的几个问题

1. 没有终止条件

这是最常见也最直接的问题。递归如果没有明确出口，就会无限调用，最终栈溢出。

2. 终止条件写错

有时不是完全没写，而是条件不够严谨，导致边界漏掉。

3. 规模没有真正缩小

如果每次递归后问题没有朝更小方向推进，那本质上还是会陷入死循环。

4. 只会“往下写”，不会“往上想”

递归最容易误解的地方，是很多人只盯着当前调用，却忘了递归真正关键的是：

子问题会返回什么；
当前层如何利用这些返回值。

5. 重复计算过多

像朴素斐波那契递归，就是典型的重复子问题很多。递归能表达问题，不代表一定高效。

十、怎么判断一个问题适不适合递归

一个问题通常在满足下面几类特征时，递归会比较自然：

可以拆成一个或多个规模更小的同类子问题；
存在清晰的最小边界情况；
问题本身具有层级结构或自相似结构；
当前层的答案可以由子问题结果组合出来。

例如：

树问题几乎天然适合递归；
分治问题通常适合递归；
回溯搜索通常也离不开递归；
一些线性扫描问题则未必需要递归。

所以不要把递归当成“逢题必用”的模板，而要把它当成一种建模方式。

十一、写递归时更稳的思考顺序

如果你刚开始练递归，可以强迫自己按这个顺序想：

1. 先定义函数含义

不要一上来就想细节流程，而先说清楚：这个函数到底解决什么问题。

2. 再找最小问题

也就是终止条件。

3. 再写递归关系

把当前问题表示成更小子问题的组合。

4. 最后再验证边界和返回值

看看是否存在漏掉的空节点、越界、重复调用或错误返回。

这个顺序非常重要，因为递归最怕的就是一开始就陷进执行细节，结果越想越乱。

十二、为什么递归是后面很多主题的入口

后面你会发现，递归几乎是这些内容的共同入口：

二叉树前中后序遍历；
树的高度、节点数、路径问题；
归并排序与快速排序；
二分查找的递归版本；
图的 DFS；
回溯、分治、动态规划中的部分问题分析。

也就是说，递归不是一个独立的小技巧，而更像是一种贯穿后续很多主题的“基础语言”。

如果这一篇不吃透，后面碰到树和图时会总觉得绕；但只要递归基础建立起来，很多看似复杂的结构题会突然变得顺理成章。

总结

递归的关键，不在于“函数调用自己”这个表面现象，而在于它提供了一种把大问题拆成小问题、再逐层组合答案的思考方式。真正值得先建立起来的，是这些核心认识：

递归适合解决结构相同、规模缩小的同类问题；
每个递归都必须有清晰的终止条件和递归关系；
递归调用的本质，是一层层进入调用栈，再一层层返回结果；
树、分治、回溯等问题之所以适合递归，是因为它们天然具有层级或自相似结构；
递归树不仅能帮助理解执行过程，也能帮助分析复杂度；
真正写递归时，最重要的是先定义函数含义，再找边界，再写关系，而不是一开始就死盯执行细节。

把这一篇理解透之后，后面再去学抽象数据类型、树结构、图遍历和分治问题时，就会越来越明显地感觉到：很多复杂问题之所以能被优雅表达，背后其实都站着递归这套思维方式。

参考资源：