How can I return values in a recursive function without stopping the recursion?

Question

I have a structure with an x amount of lists in lists, and each list an x amount of tuples. I don't know beforehand how many nested lists there are, or how many tuples in each list.

I want to make dictionaries out of all the tuples and because I don't know the depth of the lists I want to use recursion. What I did was

def tupleToDict(listOfList, dictList):
    itemDict = getItems(list)  # a function that makes a dictionary out of all the tuples in list
    dictList.append(itemDict)
    for nestedList in listOfList:
         getAllNestedItems(nestedList, dictList)

    return dictList

this works, but I end up with a huge list at the end. I would rather return the itemDict at every round of recursion. However, I don't know how to (if it is possible) return a value without stopping the recursion.

If you have a list of tuples, you can create a dictionary by simply using dict(l) on it ... — hochl
– hochl, Commented Mar 15, 2012 at 11:13

phihag · Accepted Answer · 2012-03-15 11:16:35Z

6

You're looking for yield:

def tupleToDict(listOfList):
    yield getItems(listofList)
    for nestedList in listOfList:
        for el in getAllNestedItems(nestedList):
            yield el

In Python 3.3+, you can replace the last two lines with a yield from.

You may want to rewrite your function to be iterative:

def tupleToDict(listOfList):
    q = [listOfList]
    while q:
        l = q.pop()
        yield getItems(l)
        for nestedList in listOfList:
            q += getAllNestedItems(nestedList)

answered Mar 15, 2012 at 11:16

phihag

289k75 gold badges475 silver badges489 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Niek de Klein Over a year ago

Awesome use of yield! Thanks!

Don Question Over a year ago

There may be use-cases where a generator-pattern won't be sufficient, because a lack of iterable objects. Approximation- , boundary-conditions or some fractal-algorithm comes to mind. Generators create iterables on the fly, but if you don't need an iterative, then you may have to look for another approach or refactor your original solution to match the generator-pattern. - Just a site-note to keep in mind! ;-)

John3136 · Accepted Answer · 2012-03-15 11:12:08Z

1

Who are you going to return it to? I mean if your thread is busy running the recursive algorithm, who gets the "interim results" to process?

Best bet is to tweak your algorithm to include some processing before it recurses again.

answered Mar 15, 2012 at 11:12

John3136

29.3k4 gold badges55 silver badges77 bronze badges

Comments

steve · Accepted Answer · 2012-03-15 11:19:03Z

1

I'm not sure what you're trying to do, but you could try to make a recursive generator by using the yield statement to return the dict at the desired intervals. Either that or shove copies of it into a global list?

answered Mar 15, 2012 at 11:19

steve

761 bronze badge

Comments

Don Question · Accepted Answer · 2012-03-15 11:36:04Z

1

You got two possible solutions:

The generator approach: a function with a yield statement, which may be a hassle to implement in a recursive function. (Look at phihags proposal for an example)
The callback approach: You call a helper-function/method from inside the recursion and can monitor the progress through a second outer function.

Here a non-recursive recursion example: ;-)

def callback(data): print "from the depths of recursion: {0}".format(data)



def recursion(arg, callbackfunc):
    arg += 1
    callbackfunc(arg)
    if arg <10:
        recursion(arg, callbackfunc)
    return arg

print recursion(1, callback)

answered Mar 15, 2012 at 11:36

Don Question

11.7k5 gold badges39 silver badges56 bronze badges

Collectives™ on Stack Overflow

How can I return values in a recursive function without stopping the recursion?

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related