Recursive function returning None in Python for josephus algorithm [duplicate]

Question

I'm programming the josephus algorithm.

The Josephus Problem is a mathematical problem in which a circle is made, its circumference formed of n people. Starting from the person in the 0th position, each person eliminates the person to their left (the next person in the circle). The next living person then does the same, and the process is repeated until there is only one person left alive.

I used a recursive function like this :

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))

The problem is that it's returning me None, yet when I print L[0] instead of returning it, I have this list [2,0] which is the good result, so my algorithm works. But it only return the value of the first function loopInList called (the one that get the fresh list as argument), and with this fresh list I don't go in the else statement so it's returning None. I want my first function called to return the value returned in the last function called in the recursive loop.

Yeah you're right, my bad. anyway still got my None problem :/ (it's edited btw) — ArrowRise
– ArrowRise, Commented Mar 28, 2021 at 1:11

RufusVS · Accepted Answer · 2021-03-28 01:14:19Z

0

Did you intend this (just added the return statement in the recursing block):

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))

answered Mar 28, 2021 at 1:14

RufusVS

4,1553 gold badges33 silver badges46 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

ArrowRise Over a year ago

That's it, a simple instruction missed :( I'm discovering recursion sorry^^

RufusVS Over a year ago

We all have done it. Since this has been closed, you may not be able to mark this as the answer.

Collectives™ on Stack Overflow

Recursive function returning None in Python for josephus algorithm [duplicate]

1 Answer 1

2 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Linked

Related