学习递归，理解递归

长期以来，递归一直是令我费解的概念。做此文章，谈谈我对递归的理解。

递归是什么？

递归算法在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。
这个定义源自百度百科。说实话，我看不懂。不然也不会在这个问题上花那么多时间了。
以前我对递归的理解是：说白了就是方法自己调用自己嘛。但是到了程序里就懵逼了。搞不懂里面的流程。
我天真的一步一步往里推，结果越推越乱，最后完全不清楚递归是怎么回事了。
不过最近写了一些二叉树的题，算是有了点感觉了。

递归的理解

先来一道简单题：
给定一个二叉树 root，返回其最大深度。
二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。

示例：
输入：root = [3,9,20,null,null,15,7]
输出：3

我们来看看递归的方法：

public int MaxDepth(TreeNode root) 
{
    if (root == null)
    {
        return 0;
    }
    return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
}

这题的思路是，如果我们知道了左子树的最大深度 l 和右子树的最大深度 r，那么当前树的最大深度就是 l 和 r 的较大值加 1。

而左子树和右子树的最大深度又可以用同样的方式计算。因此可以使用深度优先算法来解决这个问题。

接下来这一步，其实是我真正开始“有点懂递归”的关键。

以前我看这段代码的时候，总是忍不住去想：

MaxDepth(root.left) 里面又会调用谁？
会不会一直调下去？
每一层到底返回了什么？
是先算左边还是右边？

结果就是：脑子直接爆炸。

后来我意识到一个很重要的问题：

我用“执行过程”的方式在理解递归，但递归更适合用“定义”的方式理解。

换一种看法：把函数当成“黑盒”

我们重新看这段代码：

return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;

先不要管递归内部怎么执行。

只问一个问题：

MaxDepth(x) 这个函数，定义是什么？

答案其实很简单：

返回以 x 为根的树的最大深度

只要你接受这个定义，那这一句就很好理解了：

int left = MaxDepth(root.left);
int right = MaxDepth(root.right);
return Math.Max(left, right) + 1;

翻译成人话就是：

左子树的最大深度我已经拿到了（left）
右子树的最大深度我也拿到了（right）
当前节点的深度 = max(left, right) + 1

真正的关键转变

我后来才明白：

递归最重要的不是“它怎么一步一步执行”，而是“它帮我解决了什么问题”。

也就是说：

我不需要一开始就搞清楚所有调用过程
我只需要相信：

MaxDepth(root.left) 一定会正确返回左子树的深度

这一步非常重要。

可以说是我从“看不懂递归”到“开始能用递归”的分水岭。

那递归到底在干嘛？

用这道题总结一下，其实递归在做三件事：

1️⃣ 定义问题

MaxDepth(root)

表示：

计算以 root 为根的树的最大深度

2️⃣ 找最小子问题（终止条件）

if (root == null)
{
    return 0;
}

也就是：

空树的深度是 0

3️⃣ 把问题拆成更小的同类问题

MaxDepth(root.left)
MaxDepth(root.right)

注意这里非常关键：

子问题和原问题是“同一种问题”，只是规模更小

4️⃣ 用子问题的结果构造当前答案

return Math.Max(left, right) + 1;

为什么二叉树特别适合练递归

我后面做题的时候发现一个规律：

二叉树几乎就是为递归量身定做的结构。

因为：

每个节点下面就是一棵子树
子树的结构和整棵树完全一样

这就天然符合递归的特点：

大问题 = 左子树问题 + 右子树问题 + 当前节点处理

所以像：

最大深度
是否对称
是否相同
翻转二叉树

基本都是一眼递归。

我之前为什么会看不懂递归

回头看，其实问题主要有两个：

❌ 1. 总想把每一层都展开

比如：

MaxDepth(root) 调 MaxDepth(root.left)
又调 MaxDepth(root.left.left)
一直往下推……

结果就是：

👉 信息量太大，直接乱掉

❌ 2. 没有建立“函数定义”的意识

以前我只是觉得：

这是一个会调用自己的函数

但没有真正理解：

它“返回的结果代表什么”

一旦这一点不清楚，后面的代码就全是黑盒中的黑盒。

正确的理解方式（对我来说最有用的一点）

现在我看递归，基本只做两件事：

✔ 第一步：搞清函数定义

比如：

MaxDepth(root) —— 返回这棵树的最大深度

✔ 第二步：只看“当前层”在干嘛

int left = MaxDepth(root.left);
int right = MaxDepth(root.right);
return Math.Max(left, right) + 1;

我不会再去纠结：

left 是怎么一步一步算出来的
right 是在哪一层返回的

我只关心：

当这两行执行完时，我已经拿到了 left 和 right

然后用它们算当前结果。

一句话总结我的理解

递归不是一步一步往里推的过程，而是“相信子问题已经解决，然后在当前层拼答案”。

再回头看这道题

public int MaxDepth(TreeNode root) 
{
    if (root == null)
    {
        return 0;
    }

    return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
}

其实可以这样理解：

如果是空节点，深度是 0
否则：
- 左边的深度我交给递归去算
- 右边的深度我也交给递归去算
我只负责：
- 取最大值
- 加上当前这一层

最后的一点感受

以前我总觉得递归很“高级”，甚至有点玄学。

但现在感觉它其实很朴素：

就是把问题交给“更小的自己”去解决。

只不过一开始我们不习惯“相信这个更小的自己”。

一旦你接受了这个设定，递归反而会变得比循环更自然。