Python处理嵌套列表场景下如何将递归逻辑改写为迭代实现

非递归改写方案 #

递归调用本质是通过函数调用栈维护处理状态，我们可以手动用栈结构维护待处理的对象解析任务，同时加缓存避免重复解析、处理循环引用，完全规避递归深度限制。

完整实现代码

import typing as tp
import struct
import ctypes

# 保留原有基础类型的解析函数即可
def get_int_by_id(object_id: int) -> int:
    # 原有实现不变
    pass

def get_float_by_id(object_id: int) -> float:
    # 原有实现不变
    pass

def get_bool_by_id(object_id: int) -> bool:
    # 原有实现不变
    pass

def get_str_by_id(object_id: int) -> str:
    # 原有实现不变
    pass

def get_object_by_id(object_id: int) -> tp.Union[int, float, tuple, list, str, bool, None]:
    """
    通过id恢复对象，非递归实现
    :param object_id: 对象id
    :return: 对应id的对象，未知类型返回None
    """
    # 已解析对象缓存，key为object_id，value为解析完成的对象
    processed_cache = {}
    # 任务栈结构：(待解析对象id, 父容器对象, 父容器待填充的索引)
    stack = [(object_id, None, None)]

    while stack:
        current_id, parent, parent_idx = stack.pop()
        # 已处理过的对象直接赋值给父容器
        if current_id in processed_cache:
            if parent is not None:
                parent[parent_idx] = processed_cache[current_id]
            continue
        
        # 解析对象头获取类型信息
        header = struct.unpack("LL", ctypes.string_at(current_id, 16))
        type_id = header[1]

        # 基础类型直接解析
        if type_id == id(int):
            val = get_int_by_id(current_id)
        elif type_id == id(float):
            val = get_float_by_id(current_id)
        elif type_id == id(bool):
            val = get_bool_by_id(current_id)
        elif type_id == id(str):
            val = get_str_by_id(current_id)
        elif type_id == id(list):
            # 解析列表元信息，先创建空列表存入缓存避免循环引用
            list_header = struct.unpack("5L", ctypes.string_at(current_id, 40))
            list_len = list_header[2]
            elements_ids = struct.unpack(f"{list_len}L", ctypes.string_at(list_header[3], 8 * list_len))
            val = [None] * list_len
            processed_cache[current_id] = val
            # 倒序压入子元素任务，保证栈后进先出的特性不打乱列表顺序
            for idx in reversed(range(list_len)):
                stack.append((elements_ids[idx], val, idx))
            continue
        elif type_id == id(tuple):
            # 元组不可变，先用列表做临时占位容器
            tuple_header = struct.unpack("5L", ctypes.string_at(current_id, 40))
            tuple_len = tuple_header[2]
            elements_ids = struct.unpack(f"{tuple_len}L", ctypes.string_at(tuple_header[3], 8 * tuple_len))
            temp_container = [None] * tuple_len
            processed_cache[current_id] = temp_container
            for idx in reversed(range(tuple_len)):
                stack.append((elements_ids[idx], temp_container, idx))
            # 压入元组转换标记任务，等所有子元素解析完成后转成元组
            stack.append(("__convert_to_tuple", current_id, None))
            continue
        else:
            val = None
        
        # 处理元组转换标记任务
        if parent == "__convert_to_tuple":
            temp_container = processed_cache[current_id]
            val = tuple(temp_container)
        
        # 缓存解析结果
        processed_cache[current_id] = val
        # 赋值给父容器对应位置
        if parent is not None and parent != "__convert_to_tuple":
            parent[parent_idx] = val
    
    return processed_cache.get(object_id)

关键说明

• 不需要单独保留get_list_by_id、get_tuple_by_id函数，相关逻辑已经整合到主解析逻辑中
• 内置的processed_cache会自动处理循环引用场景，不会出现死循环，同时避免同一个id重复解析提升性能
• 理论上可以支持任意深度的嵌套结构，不会触发Python递归深度超限错误
• 如果需要多次调用解析不同的对象树，processed_cache放在函数内部每次调用自动清空，不会有内存残留问题

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