Trying mutate a variable passed by reference with a recursive function?

Question

There are better ways of finding a min in a tree but my main question is why I am unable to change record and keep track of it throughout the trace. I would prefer not to use global variables.

record = sys.maxsize
def findMin(tree, record):
        if list(tree.keys())[0] < record:
                record = list(tree.keys())[0]
        if len(tree[list(tree.keys())[0]]) == 0:
                return
        else:
                for v in tree[list(tree.keys())[0]]:
                        findMin(v, record)
findMin({100: [{40: [{34: [{15: []}]}], 56: [{67: [{13: [{9:[]}]}]}], 79: [{92: [{84:[{6:[]}]}]}]}]}
, record)
print(record)

your code return in one condititon when the length of values for key is 0, you need to imporve that — sahasrara62, May 20 '19 at 19:33
@prashantrana When it is a leaf node, stop traversing down and return. — zetologos, May 20 '19 at 19:49
Python parameters are passed by value, not by reference. Assigning to `record` doesn't affect the caller's variable. — Barmar, May 20 '19 at 19:50
@DYZ What if I wanted to keep track of both the min and the max, which do I return? — zetologos, May 20 '19 at 19:51

score 0 · Answer 1 · answered May 20 '19 at 19:55

Avoiding globals is tricky in this kind of problem. Here's one approach using python's versatile generators -

def find_min (tree):
  # recursively list all keys and values
  def values (t):
    if (isinstance(t, dict)):
      for (k,v) in t.items():
        yield k
        yield from values(v)
    elif (isinstance(t, list)):
      for v in t:
        yield from values(v)
    else:
      yield t
  # find lowest value in iterable
  def min (iter):
    a = inf
    for x in iter:
      if x < a:
        a = x
    return a
  # find lowest value in tree
  return min(values(tree))

Testing it on our tree of data -

t = {100: [{40: [{34: [{15: []}]}], 56: [{67: [{13: [{9:[]}]}]}], 79: [{92: [{84:[{6:[]}]}]}]}]}

print(find_min(t))
# 6

Trying mutate a variable passed by reference with a recursive function?

1 Answers1