CODEWITHSUNDEEP
pythontail-recursiongraph-traversal
iLurk
iLurk

Reputation: 3

Wanted some help making a function tail recursive

I made a function that flattens a dictionary object in python. An example of such an object is this:

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

The function I am using right now uses a separate list. Here is the function:

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']])

which gives the following correct output:

traverseGraph(x['items'])

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

I want to conver this function to a tail recursive function that does not use a separate list. Here is what I have, which does not work.

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']])

Here is the output:

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

I could use the list but I would prefer not to. At this point it's just more for the sake of learning. Thanks!

Upvotes: 0

Views: 71

Answers (1)

Blckknght
Blckknght

Reputation: 104762

This seems like it would work well as a recursive generator:

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']]

If you really want to stick to lists but want to return your results, you either need to be passing a results list up the chain of calls, or you need to be merging the results of your recursion into a list at each level. Here's what passing the results list up the chain of calls would look like:

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

Here's what merging would look like:

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

The merging version requires a lot more data copying, so it will be less efficient.

None of these implementations is tail recursive. You may need to recurse several times, so that's not really an option.

Upvotes: 1

Related Questions