2

In this recursive code, i'm getting the function to properly return True, but then it proceeds for 1 additional step and changes the return value to "None". I believe I don't understand return values properly. Can someone tell me why this is happening? Thank you in advance.

--

def nestedListContains(NL, target):
   for i in range(0, len(NL)):
      if type(NL[i]) == int:
         if NL[i] == target:
            return True
         elif i == (len(NL) - 1):
            return False
      elif type(NL[i]) != int:
         nestedListContains(NL[i], target)

nestedListContains([[9, 4, 5], [3, 8]], 3)   #Test Case#
Icarus
  • 23
  • 3
  • In the bottom elif case you need to have 'return nestedListContains...' that way the recursive calls know to return the functions bottom return value. – Dylan Lawrence Nov 01 '13 at 13:58
  • possible duplicate of [Weird function return value?](http://stackoverflow.com/questions/11097822/weird-function-return-value) – Ashwini Chaudhary Nov 01 '13 at 13:59

3 Answers3

1

There are three problems with your code; first, you do nothing with the result of the recursive call. Second, you should use isinstance() to check if a value is of some type, not type(ob) ==. Third, instead of using range() and check i to see if the last value was reached, just return False after the loop if nothing was found.

In total:

def nestedListContains(NL, target):
    for value in NL:
        if isinstance(value, int):
            test = value == target
        else:
            # value is not an int, so it's a list
            test = nestedListContains(value, target)
        if test:
            return True  # found target

    return False  # We finished the loop without finding target

This will throw a TypeError if NL isn't a list at all. Which is perhaps an even better check than isinstance() -- if it can be iterated then it's a list, and if iteration throws a TypeError it's something we should compare to target. I'll also make the naming a bit more standard:

def nested_list_contains(nested_list, target):
    try:
        for value in nested_list:
            if nested_list_contains(value, target):
                return True
        return False
    except TypeError:
        # It's a single value
        return nested_list == target

But there's an even better way. What we really want to do is flatten the nested list, and check to see if the target is in it. We can turn the above into a generator that flattens iterables recursively:

def flatten_nested_list(nested_list):
    try:
        for v in nested_list:
            for flattened in flatten_nested_list(v):
                yield flatten
    except TypeError:
        yield nested_list

def nested_list_contains(nested_list, target):
    return target in flatten_nested_list(nested_list)
RemcoGerlich
  • 30,470
  • 6
  • 61
  • 79
  • Thank you so much, that was such a good explanation. I've been wrestling with this for a couple days now. I knew I had the algorithm correctly but you you helped me greatly in implementing the correct code, and the reason why it was correct. – Icarus Nov 01 '13 at 15:17
0

To use recursion you have to return your recursive result:

def nestedListContains(NL, target):
   for i in range(0, len(NL)):
      if type(NL[i]) == int:
         if NL[i] == target:
            return True
         elif i == (len(NL) - 1):
            return False
      elif type(NL[i]) != int:
         #you missed the return for the recursive case
         ret = nestedListContains(NL[i], target)
         if(type(ret) == bool): #ensure we have an actual result and not a fall through
             return ret
megawac
  • 10,953
  • 5
  • 40
  • 61
  • @Icarus to address your suggested update you were misusing `isinstance` which is for inheritance see http://stackoverflow.com/questions/1549801/differences-between-isinstance-and-type-in-python – megawac Nov 01 '13 at 14:25
  • This fails if the recursive nestedListContains returns False, because then the loop has to continue. – RemcoGerlich Nov 01 '13 at 15:09
  • yep, thanks megawac, I'm still fairly new to Python, but that is way more convenient! – Icarus Nov 01 '13 at 15:21
  • @RemcoGerlich, Exacely! that was my problem, but thanks for the fix! – Icarus Nov 01 '13 at 15:22
-1

To elaborate a little on the earlier answer, you get None when you reach the end of the function without returning a specific value:

  def func():
     ... do something ...

is equivalent to:

  def func():
     ... do something ...
     return None

This will still happen if you pass in an empty NL, since there's no return statement after the loop.

(also, isinstance(value, int) is the preferred way to check the type of something)

Fredrik
  • 940
  • 4
  • 10