Recursion to determine the depth of expression

Question

I am trying to use recursion to find the depth of an “expression”, i.e. the number of layers of nested tuples: for example,

depth(('+', ('expt', 'x', 2), ('expt', 'y', 2))) => 2 depth(('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2), 1), ('/', 5, 2)))) => 4 

Basically, I decided that I needed to check (working from outside in) for each element that is an instance of a tuple, and then, if so, call the depth function recursively. But I need to find a way to figure out which set of recursive calls has the greatest depth, and what I'm stuck with. Here is what I still have:

 def depth3(expr): if not isinstance(expr, tuple): return 0 else: for x in range(0, len(expr)): # But this doesn't take into account a search for max depth count += 1 + depth(expr[x]) return count 

Thoughts on a good way to approach this?

Answer 1

You're on the right track, but instead of finding the “full” depth with count += 1 + depth(expr[x]) , use max to find the maximum:

 def depth(expr): if not isinstance(expr, tuple): return 0 # this says: return the maximum depth of any sub-expression + 1 return max(map(depth, expr)) + 1 print depth(("a", "b")) # 1 print depth(('+', ('expt', 'x', 2), ('expt', 'y', 2))) # 2 print depth(('/', ('expt', 'x', 5), ('expt', ('-', ('expt', 'x', 2), 1), ('/', 5, 2)))) # 4 

Answer 2

Only pseudocode (compilation is not guaranteed, let alone running):

  dep depth (expr):
   if not isinstance (expr, tuple):
     return 0
   else:
     mdepth = 0
     for x in range (0, len (expr)):
       d = depth (expr [x])
       if d> mdepth:
         mdepth = d
     return mdepth + 1

Answer 3

Try this here - it is a functional programming solution in the style that you will use when programming in a language such as Lisp, Haskell, etc.

 def depth(exp): if not exp: # the tuple is empty return 0 #return 0 elif not isinstance(exp[0], tuple): # first element is not a tuple return depth(exp[1:]) # traverse the rest of elements else: # depth is 1 + depth of first tuple + depth of rest of elements return 1 + max(depth(exp[0]), depth(exp[1:])) 

Answer 4

You can try this,

 def depth(expr): count = 0 if not isinstance(expr,tuple): return 0 else: count = 1 count1 = 0 for e in expr: count1 = 1 + depth(e) count = max(count1,count) return count 

Answer 5

You can simply track the last maximum depth as you go through subexpressions.

 def depth(expr): # base case if not isinstance(expr, tuple): return 0 # if it is a tuple, we've at least depth of 1 max_depth = 1 # If any sub-expression is deeper, update max_depth for elem in expr: elem_depth = 1 + depth(elem) if elem_depth > max_depth: max_depth = elem_depth return max_depth