CODEWITHSUNDEEP
pythonrecursion
Ryan
Ryan

Reputation: 1026

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 (len(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?

Upvotes: 0

Views: 379

Answers (5)

jon_darkstar
jon_darkstar

Reputation: 16778

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

Upvotes: 3

olivervbk
olivervbk

Reputation: 284

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)

Upvotes: 3

desfido
desfido

Reputation: 787

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)

Upvotes: 1

Ant
Ant

Reputation: 5424

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

Upvotes: 1

Vincent
Vincent

Reputation: 1

You are missing a return at the line where you call "findWinner"

Upvotes: 0

Related Questions