CODEWITHSUNDEEP
pythonrecursiontrackingdepth
Ishu108
Ishu108

Reputation: 103

Recursion to find depth of expression

I am trying to use recursion to find the depth of an "expression", i.e., how many layers of nested tuples there are: For example,

depth(('+', ('expt', 'x', 2), ('expt', 'y', 2))) => 2

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

Basically, I figured that I need to check (working from out to in) for each element being an instance of a tuple, and then if so, recursively call the depth function. But I need to find a way of figuring out which set of recursive calls has the greatest depth, and that's where I'm stuck. Here's what I have so far:

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?

Upvotes: 7

Views: 4869

Answers (5)

JALAL
JALAL

Reputation: 1

You can simply keep track of last maximum depth as you traverse through sub-expressions.

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

Upvotes: 0

Dhruv Mullick
Dhruv Mullick

Reputation: 561

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

Upvotes: 0

Óscar López
Óscar López

Reputation: 236004

Here, try this - it's a functional-programming solution, in the style you'd 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:]))

Upvotes: 1

John
John

Reputation: 727

Pseudocode only (not guaranteed to compile, much less run):

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

Upvotes: 0

David Robinson
David Robinson

Reputation: 78600

You're on the right track, but instead of finding the "total" 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

Upvotes: 13

Related Questions