## Return False in Recursive function

This is the place for queries that don't fit in any of the other categories.

### Return False in Recursive function

Hi there,

I can't figure out a way to return a false boolean in this function. The function: nestedListContains(NL, target): takes a nested list of integers (NL) and an integer(target) and returns true if target is in NL. I can't get it to return false when the target integer is not in any part of the list. So nestedListContains([1,2,3,4],3) = true, but nestedListContains([1,2,3,4],5) would be false.

Everything I've tried returns a false statement before the entire nested list has been checked, so it returns false when actually true.
For example, nestedListContains([[9, 4, 5], [3, 8]], 3) is returning false but nestedListContains([2, 3, 5, 7, 9], 7) will actually work properly and return True.

BTW, this is an exercise, so I'm running this in an interpreter embedded in a website that gives programmed errors.

Code: Select all
`def nestedListContains(NL, target):   if NL == target:      return NL        if isinstance(NL,list):      for i in range(0,len(NL)):         x=nestedListContains(NL[i], target)         if x==target:            return True   return False`

Program executed without crashing.
Running nestedListContains([2, 3, 5, 7, 9], 7) … its value True is correct!
Running nestedListContains([2, 3, 5, 7, 9], 8) … its value False is correct!
Running nestedListContains([[9, 4, 5], [3, 8]], 3) … Error: nestedListContains([[9, 4, 5], [3, 8]], 3) has wrong value False, expected True
Last edited by micseydel on Fri Jul 05, 2013 11:32 am, edited 1 time in total.
Reason: Locked homework-looking post.
Hypernova

Posts: 18
Joined: Mon Jun 10, 2013 12:23 am

### Re: Return False in Recursive function

Is the first if-block correct? Should your function ever return a non-boolean value, as that block causes to happen? It would be quite helpful if you posted the exact problem, or at least a URL to the problem so that we know what you're working toward. But I suspect that you should have it only return True or False, and if the input your function is supposed to be passed guarantees that the first parameter passed is list, I wouldn't be passing non-lists inside of it recursively without need either.

For recursive functions, each step is a sub-problem. So each recursive call should be a simpler, correct sub-step to the overall problem.

That said, I see no reason for you to be using indexes here. Regular Python for loops should be just fine. A minor point, but I think always worth mentioning for people who don't know better.
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Return False in Recursive function

haha I'd love to use indexes for this problem. The exercise demands that you use a recursive function though. That it returns a non-boolean value is an oversight on my part because I've only been dealing with recursion for 2 days, and was thinking about it wrongly, but now that you've pointed it out to me, I can see that it might return an integer if it the first element of a list was the target. I first thought that it wouldnt be encountered until after one recursion.

So here's the link to it:
http://cscircles.cemc.uwaterloo.ca/16-r ... n/#pybox13
Hypernova

Posts: 18
Joined: Mon Jun 10, 2013 12:23 am

### Re: Return False in Recursive function

You did use indexes. See this?
Hypernova wrote:
Code: Select all
`NL[i]`

That's you using an index. You shouldn't do it. Your block should simply be
Code: Select all
`   if isinstance(NL,list):      for element in NL:         x=nestedListContains(element, target)         if x==target:            return True`

(with a direct, mechanical change from indexes to a proper loop; as mentioned more work needs to be done to truly fix this.)

I don't believe that the for loop, using indexes or not, violates the requirement to use recursion. This problem naturally lends itself to recursion with a loop inside the function, which is just fine. In fact, your first two sentences together are quite baffling, I'm somewhat afraid of what you were thinking of doing.

When I edited your code by the way, I noticed that you're using 3 spaces for indentation by the way. 4 is more typical.
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Return False in Recursive function

hahaha, thanks for putting me straight. I'm not trying to pretend I'm any good at this I'm just determined not to give up.
Edit:With the indentation, I'm just going with the indentation level that the interpreter automatically makes. Is a typical 4 space indentation automatic in IDLE?
Last edited by Hypernova on Fri Jul 05, 2013 3:11 pm, edited 1 time in total.
Hypernova

Posts: 18
Joined: Mon Jun 10, 2013 12:23 am

### Re: Return False in Recursive function

That sounds like the right attitude.
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

### Re: Return False in Recursive function

Thanks. I'm finding this quite difficult and would be completely stuck without your help. I do apologize if my logic is flawed, recursion makes my head spin.
Hypernova

Posts: 18
Joined: Mon Jun 10, 2013 12:23 am

### Re: Return False in Recursive function

Many thanks again for your help micseydel. I managed to go from where you left me and finish off.

Cheers buddy

Code: Select all
`def nestedListContains(NL, target):   if NL == target:      return True      if isinstance(NL,list):      for element in NL:         x=nestedListContains(element, target)         if x==True:            return True   return False`
Hypernova

Posts: 18
Joined: Mon Jun 10, 2013 12:23 am

### Re: Return False in Recursive function

I still think that you're doing it a bit off. You're still passing non-list type values as the first parameter and I don't believe you should be doing it. It looks from the specs that you can assume it will be a list, and if you do that, it saves you a level of indentation and cleans up it somewhat seriously.
Due to the reasons discussed here we will be moving to python-forum.io on October 1, 2016.

This forum will be locked down and no one will be able to post/edit/create threads, etc. here from thereafter. Please create an account at the new site to continue discussion.

micseydel

Posts: 3000
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA