recursive function: use a global or pass a parameter?

Yawar Amin yawar.amin at gmail.com
Fri Jan 16 21:23:53 EST 2015


On Friday, January 16, 2015 at 1:34:51 PM UTC-5, Peter Otten wrote:
> [...]
> I recommend that you use a generator:
> 
> >>> def walk(obj):
> ...     if not hasattr(obj, "keys"):
> ...         return
> ...     if "things" in obj:
> ...         yield obj["things"]
> ...     for v in obj.values():
> ...         yield from walk(v)

Cool ... but it looks like this can still potentially hit the max
recursion limit? Perhaps better to convert to an iterative style:

    def walk(obj):
      """
      Yield any value(s) contained within `obj` that is (are) indexed by
      the key 'things'. `obj` must be dict-like.
      """
      from collections import deque
      vals = deque()
      vals.append(obj)
    
      while True:
        try: curr_obj = vals.popleft()
        except IndexError: return
        if not hasattr(curr_obj, "keys"): continue
    
        if "things" in curr_obj: yield curr_obj["things"]
        vals.extend(curr_obj.values())
    
    # Examples

    d1 = list(walk({ "things": 1, "two": { "things": 2 } }))
    
    d2 = list(walk({
      "things": 1,
      "two": { "things": 2 },
      "three":
        { "four": 4,
          "things":
            { "five": 5,
              "six": 6,
              "things":
                { "seven": 7,
                  "things": 8 } } } }))

So this effectively 'flattens' a dictionary at each level into a queue
made up of the dictionary's values, and meanwhile yields the values one
by one if they are indexed by the key 'things'.

The output for `d1` should be the same as Peter Otten's example, except
I'm using a list instead of a set because I think the yielded objects
could themselves be dictionaries or other non-hashable values.

When you're looking at the output for `d2`, remember that `walk` here
will yield _any_ object that's indexed by the key, and as I mentioned,
that could be an entire dictionary object contained within the main one.

Regards,

Yawar



More information about the Python-list mailing list