recursive method returning original value
So I'm trying to learn python on my own, and am doing coding puzzles. I came across one that pretty much ask for the best position to stand in line to win a contest. The person running the contest gets rid of people standing in odd number positions.
So for example if 1, 2, 3, 4, 5
It would get rid of the odd positions leaving 2, 4
Would get rid of the remaining odd positions leaving 4 as the winner.
When I'm debugging the code seems to be working, but it's returning [1,2,3,4,5]
instead of the expected [4]
Here is my code:
def findWinner(contestants):
if (l开发者_如何学运维en(contestants) != 1):
remainingContestants = []
for i, contestant in enumerate(contestants, 1):
if (isEven(i)):
remainingContestants.append(contestant)
findWinner(remainingContestants)
return contestants
Am I not seeing a logic error or is there something else that I'm not seeing?
You must return the value from the recurse function to the caller function:
return findWinner(remainingContestants)
else you would return just the original value without any changes.
def findWinner(contestants):
if (len(contestants) != 1):
remainingContestants = []
for i, contestant in enumerate(contestants, 1):
if (isEven(i)):
remainingContestants.append(contestant)
return findWinner(remainingContestants) # here the value must be return
return contestants # without the return above, it will just return this value(original)
How about this:
def findWinner(contestants):
return [contestants[2**int(math.log(len(contestants),2))-1]]
I know its not what the questions really about but I had to =P. I cant just look at all that work for finding the greatest power of 2 less than contestants and not point it out.
or if you don't like the 'artificial' solution and would like to actually perform the process:
def findWinner2(c):
while len(c) > 1:
c = [obj for index, obj in enumerate(c, 1) if index % 2 == 0] #or c = c[1::2] thanks desfido
return c
you shold use
return findWinner(remaingContestants)
otherwise, of course, your list will never be updated and so your func is gonna always return containts
however, see the PEP8 for style guide on python code: http://www.python.org/dev/peps/pep-0008/
the func isEven is probably an overkill...just write
if not num % 2
finally, recursion in python isn't recommended; make something like
def find_winner(alist):
while len(alist) > 1:
to_get_rid = []
for pos, obj in enumerate(alist, 1):
if pos % 2:
to_get_rid.append(obj)
alist = [x for x in alist if not (x in to_get_rid)]
return alist
Is there a reason you're iterating over the list instead of using a slice? Doesn't seem very python-y to not use them to me.
Additionally, you might want to do something sensible in the case of an empty list. You'll currently go into an infinite loop.
I'd write your function as
def findWinner(contestants):
if not contestants:
raise Exception
if len(contestants)==1:
return contestants[0]
return findWinner(contestants[1::2])
(much as @jon_darkstar's point, this is a bit tangential to the question you are explicitly asking, but still a good practice to engage in over what you're doing)
You are missing a return at the line where you call "findWinner"
精彩评论