Posted on by Kalkicode
Code Recursion

# Josephus problem using recursion

The Josephus problem is a famous theoretical problem in mathematics and computer science. It is named after the Jewish historian Flavius Josephus, who, according to the legend, found a way to avoid execution during a siege by the Romans. The problem can be stated as follows:

Suppose there are `n` people standing in a circle, numbered from `1` to `n`. Starting from person `1`, you begin counting in a fixed direction (either clockwise or counterclockwise) and skip `k-1` people. The `k-th` person is then removed from the circle. The process is repeated with the remaining `n-1` people until only one person remains, who is declared the survivor.

The task is to find the position of the survivor given the values of `n` (the number of people) and `k` (the step size to skip).

## Explanation using Example

Let's consider the test cases from the provided code:

1. Test Case 1: n = 23, k = 8

In this case, with 23 people and counting every 8th person, the survivor will be in position 2.

2. Test Case 2: n = 31, k = 4

With 31 people and counting every 4th person, the survivor will be in position 10.

3. Test Case 3: n = 34, k = 2

With 34 people and counting every 2nd person, the survivor will be in position 5.

## Pseudocode

``````josephusSolution(num, k)
if num is 1
return 1
return (josephusSolution(num - 1, k) + k - 1) % num + 1

josephus(num, k)
if num <= 0 or k <= 0
return
result = josephusSolution(num, k)
print "Number : num  K : k"
print "Result : result"
``````

## Algorithm Explanation

The `josephusSolution` function is a recursive algorithm to find the position of the survivor in the Josephus problem. It takes two parameters: `num` (the number of people in the circle) and `k` (the step size to skip). The algorithm calculates the position of the survivor recursively using the following steps:

1. If `num` is equal to 1, it means there is only one person remaining, and they are the survivor. In this case, the function returns 1.
2. Otherwise, the function calls itself recursively with `num - 1` (the remaining number of people) and `k` (the step size to skip). The result of the recursive call represents the position of the survivor in the reduced circle of `num - 1` people.
3. The algorithm then adds `k - 1` to the result of the recursive call, as this represents the number of steps to skip the next `k-th` person.
4. Finally, the algorithm takes the result modulo `num` to wrap around the circle and adds 1 to account for the 1-based indexing.

The `josephus` function handles the request to find the survivor position for a given `num` and `k`. It first checks if the inputs `num` and `k` are valid (greater than 0). If either of them is not valid, the function returns without further processing. Otherwise, it calls the `josephusSolution` function to calculate the position of the survivor and prints the given information and the calculated result.

## Program Solution

``````// C program for
// Josephus problem using recursion
#include <stdio.h>

int josephusSolution(int num, int k)
{
if (num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
void josephus(int num, int k)
{
if (num <= 0 || k <= 0)
{
// Invalid inputs
return;
}
int result = josephusSolution(num, k);
// Display given info
printf(" Number : %d  K : %d\n", num, k);
// Display calculated result
printf(" Result : %d \n", result);
}
int main(int argc, char
const *argv[])
{
// Test Case
josephus(23, 8);
josephus(31, 4);
josephus(34, 2);
return 0;
}``````

#### input

`````` Number : 23  K : 8
Result : 2
Number : 31  K : 4
Result : 10
Number : 34  K : 2
Result : 5``````
``````/*
Java Program for
Josephus problem using recursion
*/
public class Calculation
{
public int josephusSolution(int num, int k)
{
if (num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
public void josephus(int num, int k)
{
if (num <= 0 || k <= 0)
{
// Invalid inputs
return;
}
int result = josephusSolution(num, k);
// Display given info
System.out.println(" Number : " + num + " K : " + k);
// Display calculated result
System.out.println(" Result : " + result);
}
public static void main(String[] args)
{
// Test Case
}
}``````

#### input

`````` Number : 23 K : 8
Result : 2
Number : 31 K : 4
Result : 10
Number : 34 K : 2
Result : 5``````
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ Program for
Josephus problem using recursion
*/
class Calculation
{
public: int josephusSolution(int num, int k)
{
if (num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (this->josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
void josephus(int num, int k)
{
if (num <= 0 || k <= 0)
{
// Invalid inputs
return;
}
int result = this->josephusSolution(num, k);
// Display given info
cout << " Number : " << num << " K : " << k << endl;
// Display calculated result
cout << " Result : " << result << endl;
}
};
int main()
{
// Test Case
return 0;
}``````

#### input

`````` Number : 23 K : 8
Result : 2
Number : 31 K : 4
Result : 10
Number : 34 K : 2
Result : 5``````
``````// Include namespace system
using System;
/*
Csharp Program for
Josephus problem using recursion
*/
public class Calculation
{
public int josephusSolution(int num, int k)
{
if (num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (this.josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
public void josephus(int num, int k)
{
if (num <= 0 || k <= 0)
{
// Invalid inputs
return;
}
int result = this.josephusSolution(num, k);
// Display given info
Console.WriteLine(" Number : " + num + " K : " + k);
// Display calculated result
Console.WriteLine(" Result : " + result);
}
public static void Main(String[] args)
{
// Test Case
}
}``````

#### input

`````` Number : 23 K : 8
Result : 2
Number : 31 K : 4
Result : 10
Number : 34 K : 2
Result : 5``````
``````<?php
/*
Php Program for
Josephus problem using recursion
*/
class Calculation
{
public	function josephusSolution(\$num, \$k)
{
if (\$num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (\$this->josephusSolution(\$num - 1, \$k) + \$k - 1) % \$num + 1;
}
// Handles the request of finding josephus solution
public	function josephus(\$num, \$k)
{
if (\$num <= 0 || \$k <= 0)
{
// Invalid inputs
return;
}
\$result = \$this->josephusSolution(\$num, \$k);
// Display given info
echo " Number : ".\$num.
" K : ".\$k.
"\n";
// Display calculated result
echo " Result : ".\$result.
"\n";
}
}

function main()
{
// Test Case
}
main();``````

#### input

`````` Number : 23 K : 8
Result : 2
Number : 31 K : 4
Result : 10
Number : 34 K : 2
Result : 5``````
``````/*
Node JS Program for
Josephus problem using recursion
*/
class Calculation
{
josephusSolution(num, k)
{
if (num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (this.josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
josephus(num, k)
{
if (num <= 0 || k <= 0)
{
// Invalid inputs
return;
}
var result = this.josephusSolution(num, k);
// Display given info
console.log(" Number : " + num + " K : " + k);
// Display calculated result
console.log(" Result : " + result);
}
}

function main()
{
// Test Case
}
main();``````

#### input

`````` Number : 23 K : 8
Result : 2
Number : 31 K : 4
Result : 10
Number : 34 K : 2
Result : 5``````
``````#  Python 3 Program for
#  Josephus problem using recursion
class Calculation :
def josephusSolution(self, num, k) :
if (num == 1) :
#  Stop recursion process
return 1

#  Recursively finding the solution
return (self.josephusSolution(num - 1, k) + k - 1) % num + 1

#  Handles the request of finding josephus solution
def josephus(self, num, k) :
if (num <= 0 or k <= 0) :
#  Invalid inputs
return

result = self.josephusSolution(num, k)
#  Display given info
print(" Number : ", num ," K : ", k)
#  Display calculated result
print(" Result : ", result)

def main() :
#  Test Case

if __name__ == "__main__": main()``````

#### input

`````` Number :  23  K :  8
Result :  2
Number :  31  K :  4
Result :  10
Number :  34  K :  2
Result :  5``````
``````#  Ruby Program for
#  Josephus problem using recursion
class Calculation
def josephusSolution(num, k)
if (num == 1)
#  Stop recursion process
return 1
end

#  Recursively finding the solution
return (self.josephusSolution(num - 1, k) + k - 1) % num + 1
end

#  Handles the request of finding josephus solution
def josephus(num, k)
if (num <= 0 || k <= 0)
#  Invalid inputs
return
end

result = self.josephusSolution(num, k)
#  Display given info
print(" Number : ", num ," K : ", k, "\n")
#  Display calculated result
print(" Result : ", result, "\n")
end

end

def main()
#  Test Case
end

main()``````

#### input

`````` Number : 23 K : 8
Result : 2
Number : 31 K : 4
Result : 10
Number : 34 K : 2
Result : 5
``````
``````/*
Scala Program for
Josephus problem using recursion
*/
class Calculation()
{
def josephusSolution(num: Int, k: Int): Int = {
if (num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
def josephus(num: Int, k: Int): Unit = {
if (num <= 0 || k <= 0)
{
// Invalid inputs
return;
}
var result: Int = josephusSolution(num, k);
// Display given info
println(" Number : " + num + " K : " + k);
// Display calculated result
println(" Result : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Calculation = new Calculation();
// Test Case
}
}``````

#### input

`````` Number : 23 K : 8
Result : 2
Number : 31 K : 4
Result : 10
Number : 34 K : 2
Result : 5``````
``````/*
Swift 4 Program for
Josephus problem using recursion
*/
class Calculation
{
func josephusSolution(_ num: Int, _ k: Int)->Int
{
if (num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (self.josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
func josephus(_ num: Int, _ k: Int)
{
if (num <= 0 || k <= 0)
{
// Invalid inputs
return;
}
let result: Int = self.josephusSolution(num, k);
// Display given info
print(" Number : ", num ," K : ", k);
// Display calculated result
print(" Result : ", result);
}
}
func main()
{
// Test Case
}
main();``````

#### input

`````` Number :  23  K :  8
Result :  2
Number :  31  K :  4
Result :  10
Number :  34  K :  2
Result :  5``````
``````/*
Kotlin Program for
Josephus problem using recursion
*/
class Calculation
{
fun josephusSolution(num: Int, k: Int): Int
{
if (num == 1)
{
// Stop recursion process
return 1;
}
// Recursively finding the solution
return (this.josephusSolution(num - 1, k) + k - 1) % num + 1;
}
// Handles the request of finding josephus solution
fun josephus(num: Int, k: Int): Unit
{
if (num <= 0 || k <= 0)
{
// Invalid inputs
return;
}
val result: Int = this.josephusSolution(num, k);
// Display given info
println(" Number : " + num + " K : " + k);
// Display calculated result
println(" Result : " + result);
}
}
fun main(args: Array < String > ): Unit
{
// Test Case
}``````

#### input

`````` Number : 23 K : 8
Result : 2
Number : 31 K : 4
Result : 10
Number : 34 K : 2
Result : 5``````

## Time Complexity

The time complexity of the provided algorithm is `O(n)`, where `n` is the number of people in the circle. This is because the algorithm needs to calculate the survivor position recursively, and each recursive call reduces the problem size by 1.

## Resultant Output Explanation

The code correctly finds the position of the survivor for the given test cases:

1. For `n = 23` and `k = 8`, the survivor is in position 2.
2. For `n = 31` and `k = 4`, the survivor is in position 10.
3. For `n = 34` and `k = 2`, the survivor is in position 5.

The algorithm efficiently solves the Josephus problem using recursion and provides accurate results for the given inputs.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post