Требуется некоторая помощь, чтобы сделать функцию хвоста рекурсивной - PullRequest
Новая
       63

Требуется некоторая помощь, чтобы сделать функцию хвоста рекурсивной

0 голосов
/ 28 апреля 2020

Я сделал функцию, которая выравнивает объект словаря в python. Пример такого объекта: 

x = {'items': [{'name': 'Contract',
     'subItems': [{'name': 'Consultant'}, {'name': 'Direct'}]},
       {'name': 'Permanent',
        'subItems': [{'name': 'Full Time'}, {'name': 'Part Time'}]}]}

Функция, которую я сейчас использую, использует отдельный список. Вот функция: 

final_list = []
def traverseGraph(g_list, level=[]):
        for g_ in g_list:
            if 'subItems' in g_:
                traverseGraph(g_['subItems'], level+[g_['name']])
            else:
                final_list.append(level+[g_['name']])

, которая дает следующий правильный вывод: 

traverseGraph(x['items'])

final_list
[['Contract', 'Consultant'],
 ['Contract', 'Direct'],
 ['Permanent', 'Full Time'],
 ['Permanent', 'Part Time']]

Я хочу преобразовать эту функцию в хвостовую рекурсивную функцию, которая не использует отдельный список. Вот что у меня есть, но это не работает. 

def traverseGraph(g_list, level=[]):
        for g_ in g_list:
            if 'subItems' not in g_:
                return (level + [g_['name']])
            return traverseGraph(g_['subItems'], level + [g_['name']])

Вот вывод: 

a = traverseGraph(x['items'])
print(a)
['Contract', 'Consultant']

Я мог бы использовать список, но я бы предпочел не использовать. На данный момент это просто больше ради обучения. Спасибо!

1 Ответ

1 голос
/ 28 апреля 2020

Кажется, что это будет работать как рекурсивный генератор: 

def traverseGraph(g_list, level=[]):
    for g_ in g_list:
        if 'subItems' in g_:
            yield from traverseGraph(g_['subItems'], level+[g_['name']])
        else:
            yield level+[g_['name']]

Если вы действительно хотите придерживаться списков, но хотите возвращать свои результаты, вам нужно либо передать список результатов вверх цепочка вызовов, или вам нужно объединить результаты вашей рекурсии в список на каждом уровне. Вот как будет выглядеть список результатов в цепочке вызовов: 

def traverseGraph(g_list, level=[], final_list=None):
    if final_list is None:
        final_list = []
    for g_ in g_list:
        if 'subItems' in g_:
            traverseGraph(g_['subItems'], level+[g_['name']], final_list)
        else:
            final_list.append(level+[g_['name']])
    return final_list

Вот как будет выглядеть слияние: 

def traverseGraph(g_list, level=[]):
    final_list = []
    for g_ in g_list:
        if 'subItems' in g_:
            final_list.extend(traverseGraph(g_['subItems'], level+[g_['name']]))
        else:
            final_list.append(level+[g_['name']])
    return final_List

Версия слияния требует гораздо большего копирования данных, поэтому он будет менее эффективным.

Ни одна из этих реализаций не является хвостовой рекурсивной. Вам, возможно, придется повторяться несколько раз, так что это не совсем вариант.

...