3

Is there an easy way to determine the nesting level (without dependence on Python's recursion limit) of t (representing recombining binomial tree)?

t = (4, (3, 5, (2, 4, 6, (1, 3, 5, 7))))

Note that without a priori knowledge of depth of t, a routine may face recursion limit, which is set by sys.setrecursionlimit(n) and viewed by sys.getrecursionlimit(). Still, setting recursion limit very high before hand, may not be sufficient, thereby generating an error 

`RecursionError: maximum recursion depth exceeded while calling a Python object`.

The following generates a larger (deeper) t: 

t = tuple(tuple(range(k)) for k in range(1,200))`

I guess these may work (have not worked out the details):

  • one can convert t to string and count number of opening brackets
  • If flattened tuple has size $N$, then the depth has size of the positive quadratic root of $n(n+1)/2=N$, that is $n=(-1+\sqrt(1+8N))/2$
  • iteratively peel (and count) the outer container until deepest nesting
  • any others?

P.S. Any ideas why in-line TeX is not rendering in my question? Testing: $N$

user229044
  • 232,980
  • 40
  • 330
  • 338
Oleg Melnikov
  • 3,080
  • 3
  • 34
  • 65
  • 1
    Please don't make edits that make answers nonsensical. You were talking about recursion depth before the edit, so now all the answers are focusing on that. But are you actually running into a recursion depth problem? It seems like you'll only recurse once for each level of `t`, which is 4 and then 2 in your examples. – Teepeemm Nov 18 '15 at 20:55
  • Thanks for clarifying. I realized that recursion should not be a concern, so any quick approach for determining the depth should work. It made the question easier to interpret (recursion part unnecessarily complicated the question). – Oleg Melnikov Nov 18 '15 at 20:57

2 Answers2

5

You can convert the recursion function into a stack that you manage yourself, e.g.

t = (4, (3, 5, (2, 4, 6, (1, 3, 5, 7))))

def depth(t):
    max_depth = 0
    A = [(t,max_depth)]
    while A:
        x,depth = A.pop()
        if isinstance(x, (list, tuple)):
            for a in x:
                A.append((a,depth+1))
        else:
            max_depth = max(max_depth,depth)
    return max_depth

print depth(1)  # Prints 0
print depth((1,1)) # Prints 1
print depth(t) # Prints 4

This is not a recursive function so will not hit the recursion limit.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
4

Your original question talked about recursion limits being a problem, but your examples don't come anywhere close to that. I'd recommend that you take the most Pythonic approach, and only worry about recursion limits if they start to be a problem. A recursive approach to the problem is to find the depth of every element, and take the maximum.

def depth(t):
    try:
        return 1+max(map(depth,t))
    except:
        return 0

t = (4, (3, 5, (2, 4, 6, (1, 3, 5, 7))))
print(depth(t)) # 4
t = tuple(tuple(range(k)) for k in range(1,200))
print(depth(t)) # 2

This will treat a string as another nesting level, which probably isn't what you want, but may not matter.

Teepeemm
  • 4,331
  • 5
  • 35
  • 58
  • Thanks for the note. Initially, recursion limit was raising an error, but I later realized that this was related to output on screen, not the calculations. So, indeed, I'll worry about recursion limit as it becomes a problem later. – Oleg Melnikov Nov 18 '15 at 21:19