How to convert recursion to iteration when need to process nested lists?

Question

I have a function on Python get_object_by_id, that restores object by its id, calling different functions depending on the type of the object:

def get_object_by_id(object_id: int) -> tp.Union[int, float, tuple, list, str, bool]:
    """
    Restores object by id.
    :param object_id: Object Id.
    :return: An object that corresponds to object_id.

    """
    info = struct.unpack("LL", ctypes.string_at(object_id, 16))
    if info[1] == id(int):
        return get_int_by_id(object_id)
    elif info[1] == id(float):
        return get_float_by_id(object_id)
    elif info[1] == id(bool):
        return get_bool_by_id(object_id)
    elif info[1] == id(str):
        return get_str_by_id(object_id)
    elif info[1] == id(list):
        return get_list_by_id(object_id)
    elif info[1] == id(tuple):
        return get_tuple_by_id(object_id)
    else:
        return None

My function get_list_by_id restores lists recursively:

def get_list_by_id(object_id: int) -> list:
    info = struct.unpack("5L", ctypes.string_at(object_id, 40))
    size_of_list = str(info[2]) + 'L'
    elements_ides = struct.unpack(size_of_list, ctypes.string_at(info[3], 8 * info[2]))
    res_list = []
    for i in range(info[2]):
        res_list.append(get_object_by_id(elements_ides[i]))
    return res_list

It works well if nested lists are not very deep, but exceeds maximum recursion depth otherwise. I'm new to Python, and I struggle to understand, how can I rewrite this function without recursion and not make it looking monstrous.

Answer 1

Well, I didn't test it, so I don't know if it really works, but hopefully it makes the point: if the system stack won't do it, make your own stack.

def get_list_by_id(object_id: int) -> list:
    stack_im_working_on = [] # maybe dqueue is faster?
    # records are [info, elements_ides, 2=res_list, 3=i]

    def push_new_list(object_id: int) -> list:
        info = struct.unpack("5L", ctypes.string_at(object_id, 40))
        size_of_list = str(info[2]) + 'L'
        elements_ides = struct.unpack(size_of_list, ctypes.string_at(info[3], 8 * info[2]))
        res_list = []
        nonlocal stack_im_working_on
        stack_im_working_on.append([info, elements_ides, res_list, 0])

    push_new_list(object_id)            # start from working on this
    while True:                         # work from top of the stack
        info, elements_ides, res_list, i = stack_im_working_on[-1]
        while i < info[2]:
            if info[1] == id(list):             # The recursive call does not happen
                push_new_list(elements_ides[i]) # Now we work on this
                break # go to while stack_im_working_on
            else:
                res_list.append(get_object_by_id(elements_ides[i]))
                # res_list is shared with the stack frame, but i is not.
                stack_im_working_on[-1][3] = i = i + 1 # save that progress
        else: # else for while... run when it gets to the end, until NOT i < info[2](and not on break)
            # we finished this stack frame, so return the answer
            stack_im_working_on.pop() # removes last element (that we just finished)
            if stack_im_working_on:
                # return to prev stack frame (not done yet)
                stack_im_working_on[-1][2].append(res_list)
            else:
                # return to caller
                return res_list
    # Not Reached, as the only pop() checks for empty above

I hear that people don't like the "else" at the end of a loop, but it really is useful. (I always put a comment on it)
On the other hand, if your stack really won't ever be that huge, and you can predict a max size... just increase the system stack size limit. (it looks alot easier)
https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it

import sys
sys.setrecursionlimit(1500)