int josephus(int n, int k) { if (n == 1) return 1; else return (josephus(n - 1, k) + k-1) % n + 1; }

I was unable to understand the underlying recursion in it,can any please explain with an example.thanks in advance:)

int josephus(int n, int k) { if (n == 1) return 1; else return (josephus(n - 1, k) + k-1) % n + 1; }

I was unable to understand the underlying recursion in it,can any please explain with an example.thanks in advance:)

The iterative example makes it easier to understand.

Consider this Eg : n=5 and k=2.

Start from the 1st person (Let a=1). You need to kill Kth person from ‘a’. Since ‘a’ himself is the 1st person you need to kill a+(k-1)th person. ( see line 14 of my iterative code)

Now the next starting position is the person next to this dead fellow. ie. next starting position is (a+k-1) + 1.

But if dead fellow is 5, the next starting pos is 6, which is out of range for n=5. So we take (a+k-1) % (no. of remaining/alive people) + 1.

Hence for the iterative method a=(a+k-1)%i+1 , where ‘i’ represents the no. of alive people .

So basically, a+k-1 => says who will be killed.

(a+k-1)%i+1 => who will be the next person to start from.

In the final iteration that next person is obviously the winner

This can recurse as return (f(n,k-1)+k-1)%n+1 where f(1,k) = 1.

And (f(n,k-1)+k)%n works if f(1,k) = 0.

Hope this helps

1 Like