Python3中递归（OS隐式栈）与显式栈迭代的内存使用对比

优先选手动维护显式栈的迭代实现，无论是内存效率、运行稳定性还是性能都优于递归实现，具体差异如下：

内存占用差异 #

两种实现的理论时间复杂度都是O(n)、空间复杂度都是O(n)，但实际内存开销差距明显：

• 递归依赖的操作系统隐式栈，每一层调用的栈帧除了存储head节点引用外，还要保存函数返回地址、栈基址指针、寄存器上下文等额外元数据，单栈帧的开销通常是几十到上百字节（不同语言实现有差异，Python的栈帧开销约为80~100字节）。
• 迭代用的Python列表显式栈，只需要存储节点引用，64位系统下单个引用仅占8字节，相同长度的链表下，迭代的内存占用仅为递归的1/10甚至更低。
• 递归有硬性深度限制：Python默认递归深度阈值为1000，当链表长度超过该值时，递归实现会直接抛出RecursionError栈溢出错误；而迭代的显式栈分配在堆内存，只要系统内存足够，就能支持更长的链表，没有固定长度限制。

综合表现差异 #

• 运行性能：迭代更快，递归每一层都有函数调用的栈帧创建、销毁开销，迭代的append()和pop()都是O(1)均摊操作，没有额外的函数调用成本，实际运行速度比递归快30%以上。
• 可读性：递归代码更简洁，逻辑符合直觉，不需要手动维护栈结构，适合确定链表长度较短、不会触发栈溢出的场景。

示例代码逻辑说明 #

两者的核心逻辑等价，都是利用栈的后进先出特性实现反向打印：

# 递归实现（隐式栈）
class Solution:
    """Recursion"""
    def printLinkedListInReverse(self, head: "ImmutableListNode") -> None:
        if head:
            self.printLinkedListInReverse(head.getNext())
            head.printValue()

# 迭代实现（显式栈）
class Solution:
    """Iteration"""
    def printLinkedListInReverse(self, head: "ImmutableListNode") -> None:
        stack = []
        while head:
            stack.append(head)
            head = head.getNext()
        while stack:
            stack.pop().printValue()

内容的提问来源于stack exchange，提问作者abhira0