Recursion in Python, creating several new instances from each loop-CodePudding

I have a problem where I have a dictionary that contains class objects, that references one or more items. The key of the dictionary is the id of each item. I am trying to set up a recursive function for finding the chain of adjacent item IDs, for x steps.

It works, but only if there is only one item in each "adjacent_items"-variable. If there are more, it still only catches the first and moves on. In the example the "7" is never handled.

I am very new to recursive functions, but I feel like there should be an efficient way so solve this with recursion. Any input would be appreciated.

class Item:
    def __init__(self, id_num: str, adjacent: list):
        self.id = id_num
        self.adjacent_items = adjacent


def get_adjacent_x_steps(start: str, item_dict: dict, x: int, wip_set=None):
    """Get adjacent items for x steps"""

    if wip_set is None:
        wip_set = set()
    if x != 0:
        x -= 1
        for item in item_dict[start].adjacent_items:
            wip_set.add(item)
            # Todo, only takes first hit, return exits this instance..
            return get_adjacent_x_steps(item, item_dict, x, wip_set)
    else:
        return wip_set


def example():
    """Example items"""
    item1 = Item("1", ["4", "7"])
    item2 = Item("4", ["5"])
    item3 = Item("7", ["5"])
    item4 = Item("5", ["8", "17"])

    item_dict = {}
    for item in (item1, item2, item3, item4):
        item_dict[item.id] = item

    chained_items = get_adjacent_x_steps("1", item_dict, 2)

    print(chained_items)


if __name__ == '__main__':
    example()

CodePudding user response：

Try the following:

class Item:
    def __init__(self, id_num: str, adjacent: list):
        self.id = id_num
        self.adjacent_items = adjacent

def get_adjacent_x_steps(start, item_dict, x):
    if x == 0 or start not in item_dict:
        return [[]]
    return [[adj, *lst]
            for adj in item_dict[start].adjacent_items
            for lst in get_adjacent_x_steps(adj, item_dict, x - 1)]

item1 = Item("1", ["4", "7"])
item2 = Item("4", ["5"])
item3 = Item("7", ["5"])
item4 = Item("5", ["8", "17"])
item_dict = {i.id: i for i in (item1, item2, item3, item4)}

print(get_adjacent_x_steps('1', item_dict, 1))
print(get_adjacent_x_steps('1', item_dict, 2))
print(get_adjacent_x_steps('1', item_dict, 3))

Recursion happens at the list comprehension; at start, get all adjacent items (for adj in item_dict[start].adjacent_items), and apply the function to those items with one step less (get_adjacent_x_steps(adj, item_dict, x - 1)). Then return the resulting list lst along with adj.

Output:

[['4'], ['7']]
[['4', '5'], ['7', '5']]
[['4', '5', '8'], ['4', '5', '17'], ['7', '5', '8'], ['7', '5', '17']]

If you want to get the set of destinations, then you can apply a set comprehension afterwards:

print({x[-1] for x in get_adjacent_x_steps('1', item_dict, 3)})
# {'17', '8'}