Josephus problem and recursive solution in Python

In this tutorial, we will learn how to solve the Josephus problem recursively in Python.

Josephus Problem

In Josephus problem, n people are standing in a circle waiting to be executed and in every iteration, we kill the kth person and remove that person from the circle.

This procedure is repeated with the remaining people, starting with the (k+1)th person going in the same direction and killing the kth person, until only one person remains and is not killed.

We have to find the survivor position in the initial circle–given n the number of people standing in the circle initially and k the kth person to be executed.

JosephusProblem(n, k)–  represents this problem.

JosephusProblem(8, 2)– 8 people are standing in a circle and in every iteration we kill the 2nd person.

First of all, the person at position 2 is killed, then the person at position 4 is killed, then the person at position 6 is killed then the person at position 8 is killed. , Then the persons at positions 3, 5, 7 are killed. So the person at position 1 survives.

Recursive Solution

n-no of people standing in the circle

k-kth person to be killed

In every iteration, we are killing the kth person, once a person is killed n-1 person are only left.

The value of k does not change.

So we need to call JosephusProblem(n-1, k).

But the problem with this simple recursive call is–After the kth person is killed, in the reduced problem the (k+1)st person should become the 1st person.

We need to kill the kth person from the (k+1)th position now.

The (k+1)th position of the original becomes 1st position of the new recursive call.

The position which was just before the kth position i.e the (k-1)th position of the original becomes the last position i.e (n-1)th position of the new recursive call.

The positions are being shifted by k.

JosephusProblemm(n, k)           JosephusProblem(n-1, k)  –should be

(k+1)th position                           1st position

(k-1)th position                           (n-1)th position , last position

So, we can call  (JosephusProblem(n-1, k)+k)%n .

But this solution will not handle the case when Josephus(n-1, k)+k becomes n, this will give 0 as the answer.

To solve this problem we use the following recursive formula:

Josephus(n, k)=(JosephusProblem(n-1, k)+k-1)%n +1

Josephus(n-1, k)+k-1)%n will give an answer between 0 to n-1 and then finally we add 1 to it.

BASE CASE:

If only one person is left that person is the survivor, we return that person.

JosephusProblem(n, k)=1    if(n==1)

Python Code

def JosephusProblem(n , k):
    if n==1:
        return 1
    else:
        return (JosephusProblem(n-1 , k) + k-1) % n +1

print("JosephusProblem(8,2) = " , end=' ')
print(JosephusProblem(8,2))
print("JosephusProblem(7,3) = " , end=' ')
print(JosephusProblem(7,3))

OUTPUT:

JosephusProblem(8,2) = 1
JosephusProblem(7,3) = 4

 

You may also read:

Finding the power of a number using recursion in Python