python stop recursion in a function

Question

I have this function that works kind of like a tree traversal, but goes through a dictionary instead. Every key in the dict has two items in a list, so the structure is similar to a binary tree. I'm trying to find a specific key, while starting at a given key and when I find the key I want to stop my function and return the depth at which I'm at. I search through the dict find the key, but my recursive function doesn't stop at the return statement. My function:

def count(dict, key, depth):
    if key is not None:
        if key == 42:
            return depth
        return count(map, map[key][0], depth+1)
        return count(map, map[key][1], depth+1)

Tim Pierce · Accepted Answer · 2013-12-01 17:06:52Z

2

Couple problems here. One is that you have count calling itself recursively twice, once on map[key][0] and once on map[key][1]. But if the first recursive call finds the key, then presumably you can skip making the other call, right? I suspect that you want something more like this:

if key == 42:
    return depth
found = count(map, map[key][0], depth+1)
if found:
    return found
return count(map, map[key][1], depth+1)

That brings up the other problem: is there any way for count to reach the end of the map and conclude that it hasn't found the key? Are there any entries in the map which don't have valid keys in map[x][0] or map[x][1]? I think that once you've addressed that problem, the other one will become clearer too.

answered Dec 1, 2013 at 17:06

Tim Pierce

5,7041 gold badge18 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

user425495 · Accepted Answer · 2013-12-01 17:10:33Z

1

Your algorithm is incorrect for what you want to accomplish. Consider that the second recursive call to count is never invoked. Additionally, what happens for the case that your target key of 42 is not in the dictionary. I imagine you want something closer to the following function:

def find_target_depth(dict, key, target, depth):
  if key is not None:
    if key == target:
      return (True, depth)
    found, found_depth = find_target_depth(dict, dict[key][0], target, depth+1)
    if found:
      return (found,found_depth)
    return find_target_depth(dict, dict[key][1], target, depth+1)
  return (False, 0)

answered Dec 1, 2013 at 17:10

user425495

Comments

user3054997 · Accepted Answer · 2013-12-01 18:00:46Z

0

you should check your indent of your last two return.

answered Dec 1, 2013 at 18:00

user3054997

1253 silver badges10 bronze badges

Collectives™ on Stack Overflow

python stop recursion in a function

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related