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

Postby Hypernova » Fri Jul 05, 2013 10:56 am

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.

I'm not sure how to think about this. Can you share some wisdom please?
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.
The grader said:
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

Postby micseydel » Fri Jul 05, 2013 11:41 am

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.
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1354
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Return False in Recursive function

Postby Hypernova » Fri Jul 05, 2013 12:53 pm

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

Postby micseydel » Fri Jul 05, 2013 2:06 pm

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.
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1354
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Return False in Recursive function

Postby Hypernova » Fri Jul 05, 2013 2:54 pm

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

Postby micseydel » Fri Jul 05, 2013 3:06 pm

That sounds like the right attitude.
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1354
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA

Re: Return False in Recursive function

Postby Hypernova » Fri Jul 05, 2013 3:27 pm

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

Postby Hypernova » Fri Jul 05, 2013 5:51 pm

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

Postby micseydel » Sat Jul 06, 2013 12:33 am

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.
Join the #python-forum IRC channel on irc.freenode.net!

Please do not PM members regarding questions which are meant to be discussed publicly. The point of the forum is so that others can benefit from it. We don't want to help you over PMs or emails.
User avatar
micseydel
 
Posts: 1354
Joined: Tue Feb 12, 2013 2:18 am
Location: Mountain View, CA


Return to General Coding Help

Who is online

Users browsing this forum: Bing [Bot], Google [Bot] and 3 guests