递归方法返回原始值

Question

所以我正在尝试自学Python，并且正在做编码难题。我遇到过一个几乎要求排队以赢得比赛的最佳位置的人。主持比赛的人将站在奇数位置的人赶走。

例如，如果 1, 2, 3, 4, 5

它将消除奇数位置，留下 2, 4

将消除剩余的奇数位置，留下 4 作为获胜者。

当我调试代码时，代码似乎正常工作，但它返回 [1,2,3,4,5] 而不是预期的 [4]

这是我的代码：

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

我没有看到逻辑错误还是还有其他我没有看到的东西？

Answer 1

您必须将递归函数中的值返回给调用者函数：

return findWinner(remainingContestants)

否则您将仅返回原始值而不进行任何更改。

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)

Answer 2

这个怎么样：

def findWinner(contestants):
    return [contestants[2**int(math.log(len(contestants),2))-1]]

我知道这不是问题的真正内容，但我必须=P。我不能只是看着所有寻找比参赛者少 2 的最大幂的工作而不指出来。

或者如果您不喜欢“人工”解决方案并希望实际执行该过程：

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

Answer 3

你应该使用

return findWinner(remaingContestants)

其他方式，当然，你的列表永远不会更新，所以你的 func 总是会返回包含内容，

但是，请参阅 PEP8 有关 python 代码的样式指南： http://www.python.org/dev/peps/pep-0008/

func isEven 可能有点矫枉过正......

if not num % 2

最后 写一下，不建议在python中使用递归；做一些像

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

Answer 4

您迭代列表而不是使用切片是否有原因？对我来说不使用它们似乎不太Python-y。

此外，在列表为空的情况下，您可能需要做一些明智的事情。您当前将进入无限循环。

我将你的函数写为

def findWinner(contestants):
    if not contestants:
        raise Exception
    if len(contestants)==1:
        return contestants[0]
    return findWinner(contestants[1::2])

（就像@jon_darkstar的观点一样，这与你明确提出的问题有点相切，但仍然是参与你正在做的事情的一个很好的做法）

Answer 5

您在调用“findWinner”的行缺少回车符