【数据结构与算法】深入理解链表递归倒序：从“压栈”到“出栈”的本质剖析
理解链表倒序遍历的核心，在于看透递归背后的“函数调用栈”机制。只要理清代码的执行顺序与状态保存，倒序逻辑将一目了然。
一、 核心结论：递归即隐式栈操作
代码中的递归调用traverse(head.next)，底层等价于手动维护一个“系统调用栈”。
- 压栈（递）：每深入一层递归，当前函数的状态（包括参数、执行位置）会被自动压入栈底等待。
- 出栈（归）：当遇到终止条件（如
head == null）时，开始逐层弹栈并返回，继续执行之前被暂停的代码。
二、 代码逻辑拆解
以链表1 -> 2 -> 3 -> null的倒序遍历代码为例：
java
void traverse(ListNode head) {
if (head == null) return; // 1. 终止条件
traverse(head.next); // 2. 压栈：向下深入
System.out.println(head.val); // 3. 出栈：回溯时执行打印
}
关键点：traverse(head.next)是一句完整的函数调用。程序必须等待该函数彻底执行完毕并返回后，才会继续向下执行print语句。
三、 执行过程全景推演
1. 压栈阶段（不断向下，冻结打印指令）
- 调用
traverse(1)：print(1)被暂停，压栈等待。 - 调用
traverse(2)：print(2)被暂停，压栈等待。 - 调用
traverse(3)：print(3)被暂停，压栈等待。 - 调用
traverse(null)：触发return，直接返回。
此时系统栈（从底到顶）：traverse(1)->traverse(2)->traverse(3)。
所有print操作均被挂起。
2. 出栈阶段（回溯与返回的本质）
traverse(null)返回，回到traverse(3)。关键点：返回到了当初调用它的那一行，即traverse(head.next);。因为这一行已经执行完毕，程序自然继续往下走，执行print(3)。（首次打印：3）traverse(3)执行完毕返回，回到traverse(2)的traverse(head.next);这一行。执行完毕，继续往下走，执行print(2)。（第二次打印：2）traverse(2)执行完毕返回，回到traverse(1)的traverse(head.next);这一行。执行完毕，继续往下走，执行print(1)。（第三次打印：1）
最终输出顺序为3、2、1，实现倒序。
四、 本质总结
- 正序（前序）：打印代码写在递归调用之前。节点一进来就处理，自然是头到尾。
- 倒序（后序）：打印代码写在递归调用之后。必须等后面的节点全部处理完（全部出栈），当前节点才能执行打印。
利用系统栈“先进后出”的特性，单链表的倒序遍历无需额外数据结构即可优雅实现。
延伸思考验证：
若代码逻辑调整为：
java
void traverse(ListNode head) {
if (head == null) return;
System.out.println(“A:” + head.val); // 前序位置
traverse(head.next);
System.out.println(“B:” + head.val); // 后序位置
}
对于链表1 -> 2 -> 3，输出将是：
text
A:1
A:2
A:3
B:3
B:2
B:1
若能瞬间推导此结果，则说明已彻底掌握递归的执行时序与栈的回溯本质。