1. 项目概述为什么链表递归值得单开一篇总结刷LeetCode的朋友尤其是主攻C的对链表肯定不陌生。从反转链表、合并有序链表到判断环、找交点链表题是面试中的常客也是考察指针操作和递归思维的绝佳载体。很多人刷链表题一开始习惯用迭代——设个dummy头节点然后用prev、curr、next三个指针在链表上“翻腾”逻辑直观但代码往往显得冗长边界条件处理起来也容易出错。递归则是另一种截然不同的解题视角。它不直接操作指针的“下一步”而是把问题分解成更小的子问题相信函数能解决子问题然后基于子问题的结果构建原问题的答案。对于链表这种天然具有递归结构一个节点指向下一个节点下一个节点又指向下下个节点的数据结构递归解法常常能写出极其简洁、优雅的代码有时甚至是“降维打击”。但递归也让不少人头疼递归函数怎么写递归基终止条件怎么定如何理解递归调用的顺序和返回值内存开销会不会很大这篇总结就是把我自己在LeetCode上用C刷链表题时关于递归解法的经验、套路和踩过的坑系统地梳理出来。它不是简单的题解罗列而是试图提炼出递归求解链表问题的通用思维模型和代码模板。无论你是正在为面试突击还是想深化对递归和链表的理解相信这些从实战中总结出的“心法”都能让你在遇到新题时多一种清晰、有力的解题武器。2. 递归解链表问题的核心思维拆解2.1 递归的两种视角递去与归来理解链表递归首先要建立两个清晰的视角“递去”的过程和“归来”的过程。我们以最经典的反转链表为例。迭代思维是我站在当前节点需要改变它的next指针指向它的前驱。所以我需要记录前驱(prev)、当前(curr)和后继(next)然后一步步移动。递归思维则完全不同。它的核心思想是我不需要亲自从链表头走到尾去反转所有指针我只需要相信我的函数能帮我反转从下一个节点开始的子链表。具体来说“递去”阶段函数从链表头节点head开始不断递归调用自身参数是head-next。这个过程一路深入到链表的最后一个节点或空节点。在这个过程中我们“暂时”什么都不做只是不断地把问题规模缩小链表变短。“归来”阶段当递归到最深处链表尾开始返回时我们拿到了已经反转好的、从原链表第二个节点开始的子链表的新头节点假设叫newHead。此时关键的一步发生了我们需要让当前节点head成为这个已反转子链表的最后一个节点。怎么做就是让head-next原链表中的下一个节点现在在已反转子链表中是最后一个节点的next指针指向当前节点head即head-next-next head。然后别忘了把当前节点head的next置为nullptr避免成环。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { // 递归基空链表或只有一个节点无需反转直接返回 if (head nullptr || head-next nullptr) { return head; } // 递归调用反转以head-next开头的子链表并相信它能返回新头节点 ListNode* newHead reverseList(head-next); // 归来阶段的核心操作让当前节点成为已反转子链表的尾节点 head-next-next head; // 关键 head-next nullptr; // 关键 // 返回新的头节点它来自于最深层的递归调用原链表的尾节点 return newHead; } };这段代码的精髓在于head-next-next head。在“归来”时head是当前层递归的节点head-next是下一层递归反转后的子链表的尾节点因为下一层返回的是新头但当前层的head-next还指向这个尾。我们让这个尾节点的next指向当前节点head就完成了局部反转。最后新的头节点newHead被一层层原封不动地返回给最外层的调用者。注意递归反转链表的空间复杂度是O(n)因为递归深度等于链表长度。对于超长链表存在栈溢出风险。面试时需权衡通常迭代法的O(1)空间是更安全的选择。但递归的思维价值远超于此。2.2 递归函数设计的四要素设计一个递归函数来解决链表问题通常离不开下面四个要素我把它称为“递归四板斧”返回值 (Return Type)想清楚这个递归函数需要返回什么。是返回新链表的头节点还是返回某个布尔值如是否回文或者是返回一个包含多个信息的结构体/对组如判断平衡二叉树时返回高度和是否平衡对于链表最常返回的就是ListNode*。参数 (Parameters)除了链表节点本身递归还需要哪些额外信息有时需要前驱节点如某些删除操作有时需要记录长度或位置。如果原函数接口参数不够可以定义辅助递归函数。终止条件 (Base Case)也称为递归基。这是递归的出口必须清晰无误。对于链表常见的终止条件有if (head nullptr): 空链表。if (head-next nullptr): 链表只剩下一个节点。有时也可能是到达特定位置如if (n 0)在递归删除倒数第N个节点时。单层递归逻辑 (Recursive Logic)这是最核心的部分。在这一层递归调用中你需要相信递归函数能正确解决子问题通常是head-next相关的问题。根据子问题的结果结合当前节点head构造出当前层问题的结果。处理好当前节点和子问题结果之间的连接关系。以合并两个有序链表为例递归解法异常简洁class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { // 终止条件任一链表为空直接返回另一个链表 if (list1 nullptr) return list2; if (list2 nullptr) return list1; // 单层递归逻辑选择当前值较小的节点作为头并将其next指向剩余部分合并的结果 if (list1-val list2-val) { list1-next mergeTwoLists(list1-next, list2); // 相信递归能合并剩下的 return list1; // 当前较小的节点是合并后链表的头 } else { list2-next mergeTwoLists(list1, list2-next); return list2; } } };这里的“相信”非常关键我不需要知道mergeTwoLists(list1-next, list2)具体是怎么合并的我只需要知道它返回的是合并后链表的正确头节点然后我让list1-next指向它就行了。2.3 链表递归 vs. 树递归链表是线性结构树是分叉结构但它们的递归有很强的相似性对比理解有助于加深印象。相似点都依赖于将问题分解为更小的、结构相似的子问题。链表是head和head-next二叉树是root、root-left和root-right。都需要明确的终止条件链表空/树空。关键区别递归方向链表递归通常是单向的、线性的一直向next方向深入。树递归则可能是多路的先左后右或者各种遍历顺序。子问题数量链表每层递归通常只有一个明确的子问题处理head-next。二叉树每层递归通常有两个子问题处理左子树和右子树。结果组合链表递归的结果组合通常很简单就是把当前节点和子问题返回的链表连接起来。树递归的结果组合可能更复杂需要比较左右子树的结果或者进行某种计算如求最大深度是max(left, right) 1。理解这个区别能帮你快速判断一个问题是否适合用递归以及递归函数的大致骨架应该怎么写。3. 高频题型递归解法套路与实现掌握了核心思维我们来看几类高频链表题的递归解法。我会给出代码并重点解释递归函数的设计和单层逻辑。3.1 反转类问题反转链表是递归的“入门必修课”。除了整个反转还有局部反转、按组反转等变种。3.1.1 反转整个链表上文已给出经典解法。其核心是让当前节点的后继节点指向自己。关键在于理解head-next-next head这行代码执行时head-next在子问题中已经被反转成了尾节点。3.1.2 反转链表的一部分 (LeetCode 92)反转从位置left到right的链表。递归思路可以很巧妙。class Solution { public: ListNode* successor nullptr; // 后驱节点记录第right1个节点 // 反转链表前n个节点并返回新的头节点 ListNode* reverseN(ListNode* head, int n) { if (n 1) { // 记录第n1个节点即不需要反转部分的后继 successor head-next; return head; } // 反转以head-next开头的前n-1个节点 ListNode* last reverseN(head-next, n - 1); // 将当前节点连接到已反转部分的后面 head-next-next head; // 当前节点反转后应连接到后继节点successor head-next successor; return last; } ListNode* reverseBetween(ListNode* head, int left, int right) { if (left 1) { // 如果从第一个节点开始反转就是反转前right个节点 return reverseN(head, right); } // 如果left1则问题转化为反转head-next链表中从left-1到right-1的部分 head-next reverseBetween(head-next, left - 1, right - 1); return head; } };这个解法体现了递归的“魔力”。reverseBetween函数通过不断递归将left和right的索引向前推进直到left变为1转化为反转前n个节点的子问题。而reverseN函数在反转前n个节点时巧妙地用successor全局变量记录了不需要反转的后继部分并在反转完成后将新尾节点即原head连接到successor。这种“分解连接”的思想非常经典。实操心得处理局部反转时一定要想清楚反转后的新尾节点应该接上哪一部分。使用一个successor或prev这样的变量来记录连接点是常见的技巧。3.2 删除类问题删除操作需要小心处理节点释放C和指针更新。递归可以让逻辑更清晰。3.2.1 删除链表中等于给定值的所有节点 (LeetCode 203)class Solution { public: ListNode* removeElements(ListNode* head, int val) { // 终止条件空链表 if (head nullptr) return nullptr; // 递归处理后续链表 head-next removeElements(head-next, val); // 归来后判断当前节点是否需要删除 // 如果当前节点值等于val则跳过当前节点返回已处理好的后续链表头 // 否则返回当前节点其next已指向处理好的后续链表 return head-val val ? head-next : head; } };这个解法的精妙之处在于它把“判断是否删除当前节点”的逻辑放在了递归调用之后即“归来”阶段。我们先相信递归能把head-next之后的链表处理好删除了所有值为val的节点并返回处理后的新头节点。然后我们再看当前head节点本身如果它的值等于val那么它就应该被删除所以我们直接返回head-next即处理好的后续链表如果不等于就让head-next指向处理好的后续链表并返回head本身。这样删除操作就通过指针的重新赋值自然完成了。3.2.2 删除排序链表中的重复元素 II (LeetCode 82)删除所有重复数字的节点只保留原始链表中没有重复出现的数字。这道题用递归可以避免复杂的双指针迭代。class Solution { public: ListNode* deleteDuplicates(ListNode* head) { // 终止条件空链表或单节点链表 if (head nullptr || head-next nullptr) return head; ListNode* nextNode head-next; // 如果当前节点与下一个节点值相同 if (head-val nextNode-val) { // 一直跳过所有值相同的节点 while (nextNode ! nullptr head-val nextNode-val) { nextNode nextNode-next; } // 此时nextNode是第一个值不同的节点或者nullptr // 当前节点head及其后所有值相同的节点都应被删除 // 所以直接递归处理nextNode开始的链表并返回其结果 return deleteDuplicates(nextNode); } else { // 如果当前节点与下一个节点值不同则保留当前节点 // 递归处理后续链表并将结果接在当前节点后面 head-next deleteDuplicates(head-next); return head; } } };这里递归函数承担了两个职责1. 判断当前节点是否重复2. 决定是跳过删除当前节点还是保留。当发现重复时用一个循环跳过所有重复节点然后直接递归处理剩下的部分相当于把当前这一段重复节点整体丢弃。这种“整体处理”的思维用递归表达非常自然。3.3 合并与排序类问题合并两个有序链表是递归的典范。升级版是合并K个有序链表递归思路分治同样高效。3.3.1 合并两个有序链表上文已给出代码。其本质是每次比较两个链表的头取小的那个然后问题规模缩小被取走的链表指针后移递归合并剩下的部分。3.3.2 合并K个升序链表 (LeetCode 23)暴力两两合并效率低。递归分治是O(NlogK)的优美解法。class Solution { public: // 辅助函数合并两个链表递归版 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } } // 分治合并函数将链表数组lists在区间[left, right]内合并 ListNode* mergeKListsHelper(vectorListNode* lists, int left, int right) { // 终止条件区间内只有一个链表直接返回 if (left right) return lists[left]; // 终止条件区间无效返回空 if (left right) return nullptr; // 分治找到中点分别合并左右两半最后合并两个结果 int mid left (right - left) / 2; ListNode* leftMerged mergeKListsHelper(lists, left, mid); ListNode* rightMerged mergeKListsHelper(lists, mid 1, right); return mergeTwoLists(leftMerged, rightMerged); } ListNode* mergeKLists(vectorListNode* lists) { if (lists.empty()) return nullptr; return mergeKListsHelper(lists, 0, lists.size() - 1); } };这个解法是“递归套递归”。mergeKListsHelper是一个分治递归它把K个链表的合并问题分解成两个子问题合并左半部分K/2个链表合并右半部分K/2个链表然后再调用mergeTwoLists这个递归函数来合并两个子问题的结果。分治递归的树状结构保证了高效的合并顺序避免了重复比较。3.4 判断与查找类问题这类问题往往需要递归函数返回更多信息或者利用递归的“归来”阶段进行判断。3.4.1 回文链表 (LeetCode 234)要求O(n)时间和O(1)空间递归并非最优解因为递归栈空间是O(n)但其思路极具启发性。class Solution { public: ListNode* frontPointer; // 前向指针用于与递归“归来”的节点比较 bool recursivelyCheck(ListNode* currentNode) { if (currentNode ! nullptr) { // 递归深入到链表尾部 if (!recursivelyCheck(currentNode-next)) { return false; // 如果子链表不是回文提前返回false } // “归来”阶段比较当前节点从尾部回溯和前向指针节点 if (currentNode-val ! frontPointer-val) { return false; } // 前向指针后移 frontPointer frontPointer-next; } // 空节点或比较通过返回true return true; } bool isPalindrome(ListNode* head) { frontPointer head; return recursivelyCheck(head); } };这个解法巧妙地利用了递归栈的“后进先出”特性。recursivelyCheck函数先一路递归到链表末尾currentNode为nullptr时开始返回。在返回的过程中currentNode实际上是从链表尾部向头部回溯。同时我们用一个全局的frontPointer从链表头部向尾部移动。在每一层递归返回时我们比较currentNode-val和frontPointer-val如果都相等链表就是回文的。这相当于用递归模拟了一个反向指针。3.4.2 相交链表 (LeetCode 160)寻找两个链表的相交节点。递归解法不如双指针法直观高效但作为一种思维练习很有意思。思路是同时递归遍历两个链表当到达末尾时切换到另一个链表的头部继续。这需要修改链表结构或使用额外标记实践中不推荐但可以帮助理解递归遍历的同步性。4. 递归的代价、优化与替代方案递归写法简洁但并非没有代价。在实际编码和面试中必须清醒地认识到以下几点。4.1 空间复杂度隐形的栈开销这是递归最显著的缺点。每个递归调用都会在内存的调用栈中压入一帧用于保存参数、局部变量和返回地址。对于长度为n的链表递归深度就是n因此空间复杂度是O(n)。相比之下迭代解法通常只需要几个指针变量空间复杂度是O(1)。风险当链表非常长时例如几万、几十万个节点递归可能导致栈溢出Stack Overflow程序崩溃。面试提示即使你写出了漂亮的递归解也最好能主动提及这一点并说明迭代解的空间优势。这体现了你的全面思考。4.2 时间复杂度与重复计算对于链表递归时间复杂度通常和迭代法相同都是O(n)因为每个节点只被访问一次。但在一些更复杂的问题如某些树形DP问题中朴素的递归可能导致大量重复计算这时就需要用到记忆化搜索Memoization或动态规划来优化。链表递归中这种情况较少。4.3 何时选择递归决策指南根据我的经验可以遵循以下决策路径问题是否具有递归结构链表、树、图、分治、回溯等问题天然适合递归。递归解法是否显著更简洁、更易理解对于合并、反转、删除等操作递归代码往往比迭代更短逻辑更清晰。数据规模是否可控如果链表长度明确不会很大比如面试题通常不会超过10^4递归的栈开销可以接受。是否需要考虑极致性能在要求O(1)空间的场景如面试官明确要求或者在线判题系统对内存有严格限制时应优先选择迭代。一个实用的建议在面试中可以先快速给出递归解法展示你对问题和递归思维的理解。然后如果时间允许或面试官追问再补充迭代解法并对比两者的优缺点。这能充分展示你的技术广度和深度。4.4 从递归到迭代的转换技巧理解递归和迭代的对应关系能帮助你双向打通。很多递归算法都可以通过显式地使用栈Stack来模拟递归调用过程从而转化为迭代算法。例如二叉树的中序遍历递归写法很简单void inorder(TreeNode* root) { if (!root) return; inorder(root-left); visit(root); inorder(root-right); }其迭代写法就是用栈手动模拟这个过程void inorder(TreeNode* root) { stackTreeNode* stk; TreeNode* curr root; while (curr ! nullptr || !stk.empty()) { while (curr ! nullptr) { // 模拟递归左子树深入 stk.push(curr); curr curr-left; } curr stk.top(); stk.pop(); // 模拟递归返回访问节点 visit(curr); curr curr-right; // 转向右子树 } }对于链表递归虽然通常不需要用栈来模拟因为线性递归容易改成循环但理解这种“栈模拟递归”的思想对于理解程序执行机制和解决更复杂问题很有帮助。5. 进阶挑战与递归思维扩展掌握了基本套路后可以尝试一些更复杂的问题锻炼递归思维的灵活性。5.1 复杂递归两两交换链表中的节点 (LeetCode 24)给定一个链表两两交换其中相邻的节点并返回交换后的链表。你不能只是单纯改变节点内部的值而是需要实际进行节点交换。递归解法清晰体现了“相信递归能处理好子问题”的思想class Solution { public: ListNode* swapPairs(ListNode* head) { // 终止条件没有节点或只有一个节点无法交换 if (head nullptr || head-next nullptr) { return head; } // 要交换的两个节点是head和head-next ListNode* firstNode head; ListNode* secondNode head-next; // 递归交换以secondNode-next开始的后续链表并相信它能返回新头 ListNode* swappedSubList swapPairs(secondNode-next); // 进行交换第二个节点指向第一个节点 secondNode-next firstNode; // 第一个节点指向已经交换好的后续子链表 firstNode-next swappedSubList; // 新的头节点是原来的第二个节点 return secondNode; } };单层递归逻辑当前层负责交换前两个节点firstNode和secondNode。我们相信递归调用swapPairs(secondNode-next)能正确处理好剩下的所有节点对。然后我们只需要把当前这对节点交换并连接到处理好的子链表上即可。这种“先处理子问题再处理当前问题”的模式非常普遍。5.2 递归与全局变量/成员变量在一些问题中递归函数需要访问或修改一个在递归过程中需要持续追踪的状态。这时可以使用全局变量或类的成员变量。示例重排链表 (LeetCode 143)给定一个单链表 LL0 → L1 → … → Ln-1 → Ln将其重新排列为L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → … 一种递归思路是我们用一个指针从左侧开始递归函数从右侧开始回溯在回溯过程中进行穿插连接。class Solution { public: ListNode* left; // 左侧指针 bool stop; // 停止标志 void reorderHelper(ListNode* right) { if (right nullptr) return; // 递归基到达链表尾 // 先递归到最右边 reorderHelper(right-next); // 如果已经完成重排或者左右指针相遇/交错则停止 if (stop) return; if (left right || left-next right) { right-next nullptr; stop true; return; } // 核心操作穿插节点 ListNode* nextLeft left-next; left-next right; right-next nextLeft; left nextLeft; // 左侧指针后移 } void reorderList(ListNode* head) { if (head nullptr) return; left head; stop false; reorderHelper(head); } };这里left和stop作为成员变量在递归过程中被所有递归层共享和修改。reorderHelper函数递归到链表末尾然后在回溯过程中right指针从尾向头移动与从头向尾移动的left指针配合完成节点的穿插。当left和right相遇或即将交错时设置stop标志终止后续操作。这种使用外部状态辅助递归的技巧在解决一些需要“左右对撞”或“前后配合”的问题时非常有用。5.3 多任务递归扁平化多级双向链表 (LeetCode 430)这道题虽然不是单链表但递归思路非常经典。每个节点可能有子链表需要将多级链表扁平化。递归函数flatten可以设计为给定一个头节点扁平化以它开始的链表并返回扁平化后的尾节点。这样在每一层递归中如果当前节点有子链表我们可以先递归扁平化子链表得到子链表的尾节点然后将其插入到当前节点和当前节点的下一个节点之间。class Node { public: int val; Node* prev; Node* next; Node* child; }; class Solution { public: Node* flatten(Node* head) { if (!head) return nullptr; flattenHelper(head); return head; } // 辅助函数扁平化链表并返回扁平化后的尾节点 Node* flattenHelper(Node* node) { Node* curr node; Node* tail node; // 记录当前链表的尾节点 while (curr) { Node* nextNode curr-next; // 保存下一个节点 if (curr-child) { // 递归扁平化子链表得到其头尾 Node* childHead curr-child; Node* childTail flattenHelper(curr-child); // 将子链表插入当前节点和nextNode之间 curr-next childHead; childHead-prev curr; childTail-next nextNode; if (nextNode) { nextNode-prev childTail; } // 清除child指针 curr-child nullptr; // 更新尾节点为子链表的尾或nextNode为空时就是子链表尾 tail childTail; } else { // 没有子链表尾节点就是当前节点 tail curr; } curr nextNode; // 处理下一个节点 } return tail; // 返回扁平化后的尾节点 } };这个递归函数flattenHelper的返回值是尾节点这使得上一层递归能够方便地将扁平化的子链表“拼接”到主链表中。它实际上是在进行一种深度优先的遍历DFS遇到子链表就深入进去处理完后再回来继续处理主链表。这种“返回尾节点”的设计避免了为了找尾节点而再次遍历提高了效率。6. 调试技巧与常见“坑点”实录递归代码逻辑抽象调试起来有时不如迭代直观。分享几个我实践中总结的调试方法和常见错误。6.1 如何调试递归函数画递归树/调用栈图这是最有效的方法。在纸上画出每一层递归调用时函数的参数head指向哪个节点、局部变量的状态。特别是“归来”阶段标出每一步操作后指针的变化。对于反转链表画图能让你瞬间理解head-next-next head在做什么。添加打印语句在递归函数的入口和返回前添加打印输出当前层的关键信息如head-val递归深度等。这能帮你直观看到递归的“递去”和“归来”顺序。ListNode* reverseList(ListNode* head, int depth) { cout - depth: depth , head: (head ? to_string(head-val) : null) endl; if (!head || !head-next) return head; ListNode* newHead reverseList(head-next, depth 1); head-next-next head; head-next nullptr; cout - depth: depth , head: head-val , newHead: newHead-val endl; return newHead; }使用IDE调试器设置条件断点观察调用栈Call Stack的展开和收缩过程。重点关注递归基是否被正确触发以及“归来”阶段每层局部变量的值是否符合预期。小规模测试先用一个极短的链表如1-2-3测试手动模拟每一步验证结果。6.2 递归解链表题的常见“坑”忘记处理递归基Base Case这是最常见的错误。递归基必须能够终止递归。对于链表通常要处理head nullptr和head-next nullptr的情况。如果漏掉会导致访问空指针的next成员引发运行时错误。指针操作顺序错误在“归来”阶段进行指针重新赋值时顺序至关重要。例如在反转链表中如果先执行head-next nullptr再执行head-next-next head就会因为head-next已经是nullptr而访问空指针。务必先保存必要的信息再进行修改。对递归返回值理解错误递归函数返回的是什么是子问题处理后的新头节点还是尾节点或者是其他信息必须清晰理解并正确使用这个返回值。例如在合并链表递归中list1-next mergeTwoLists(...)这里递归返回的是合并后子链表的头我们必须把它正确连接到list1后面。忽略递归的副作用有些递归函数会修改输入链表的结构。如果你还需要原始链表就需要在递归前进行拷贝或者使用不修改原链表的递归方式通常效率较低。空间复杂度误判误以为递归解法空间复杂度是O(1)。一定要记住递归调用栈的空间开销。6.3 递归与迭代的等价转换练习最好的学习方法之一是将递归代码改写成迭代代码反之亦然。这里给出反转链表的迭代版本作为对比// 递归版本 (简洁但空间O(n)) ListNode* reverseListRecursive(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseListRecursive(head-next); head-next-next head; head-next nullptr; return newHead; } // 迭代版本 (稍长但空间O(1)) ListNode* reverseListIterative(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* nextTemp curr-next; // 保存下一个节点 curr-next prev; // 反转指针 prev curr; // prev和curr前移 curr nextTemp; } return prev; // 循环结束时prev指向新的头节点 }对比两者迭代版本需要手动维护prev,curr,nextTemp三个指针清晰地模拟了反转过程。而递归版本则将“保存下一个节点”和“移动指针”这些步骤隐含在了递归调用栈中。理解这种等价性能让你真正掌握这两种思维模式。