python - 约瑟夫斯算法在Python中返回None的递归函数

Question

我正在编写约瑟夫斯算法。

约瑟夫斯问题是一个数学问题，其中有一个圆，它的圆周由 n 个人组成。从第 0 位的人开始，每个人淘汰他们左边的人（圆圈中的下一个人）。然后下一个活着的人做同样的事情，重复这个过程，直到只剩下一个人活着。

我使用了这样的递归函数：

def loopInList(L):
    if len(L)>1:
        i=0
        while i < len(L) - 1 :
            L.remove(L[i+1])
            i += 1 
        loopInList(L[i:] + L[:i])
    else:
        return L[0]
        
def josephus(n):
    L = [x for x in range(n)]
    return loopInList(L)
print(josephus(9))

问题是它正在返回 me None，但是当我打印L[0]而不是返回它时，我有这个列表[2,0]，这是一个很好的结果，所以我的算法有效。但它只是调用return的第一个函数的值loopInList（将新列表作为参数的那个），并且对于这个新列表，我不会进入else语句，所以它返回 None。我希望我的第一个函数调用返回在递归循环中调用的最后一个函数中返回的值。

标签： pythonrecursion

Answer 1

您是否打算这样做（只是在递归块中添加了 return 语句）：

def loopInList(L):
    if len(L)>1:

        i=0
        while i < len(L) - 1 :
            L.remove(L[i+1])
            i += 1 
        return loopInList(L[i:] + L[:i])
    else:
        return L[0]
        
def josephus(n):
    L = [x for x in range(n)]
    return loopInList(L)
print(josephus(9))