Skip to main content

Josephus problem using recursion

The Josephus problem is a mathematical problem that involves a group of people standing in a circle, where one person is eliminated in each iteration until only one person remains. The problem is to determine the position of the last person standing.

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)
	{
		Calculation task = new Calculation();
		// Test Case
		task.josephus(23, 8);
		task.josephus(31, 4);
		task.josephus(34, 2);
	}
}

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()
{
	Calculation *task = new Calculation();
	// Test Case
	task->josephus(23, 8);
	task->josephus(31, 4);
	task->josephus(34, 2);
	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)
	{
		Calculation task = new Calculation();
		// Test Case
		task.josephus(23, 8);
		task.josephus(31, 4);
		task.josephus(34, 2);
	}
}

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()
{
	$task = new Calculation();
	// Test Case
	$task->josephus(23, 8);
	$task->josephus(31, 4);
	$task->josephus(34, 2);
}
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()
{
	var task = new Calculation();
	// Test Case
	task.josephus(23, 8);
	task.josephus(31, 4);
	task.josephus(34, 2);
}
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() :
	task = Calculation()
	#  Test Case
	task.josephus(23, 8)
	task.josephus(31, 4)
	task.josephus(34, 2)

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() 
	task = Calculation.new()
	#  Test Case
	task.josephus(23, 8)
	task.josephus(31, 4)
	task.josephus(34, 2)
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
		task.josephus(23, 8);
		task.josephus(31, 4);
		task.josephus(34, 2);
	}
}

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()
{
	let task: Calculation = Calculation();
	// Test Case
	task.josephus(23, 8);
	task.josephus(31, 4);
	task.josephus(34, 2);
}
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
{
	val task: Calculation = Calculation();
	// Test Case
	task.josephus(23, 8);
	task.josephus(31, 4);
	task.josephus(34, 2);
}

input

 Number : 23 K : 8
 Result : 2
 Number : 31 K : 4
 Result : 10
 Number : 34 K : 2
 Result : 5
Last updated on by Kalkicode




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.

New Comment