Josephus problem (recursive)

Question

This is the resolution, recursively made in C++, of josephus problem, where n is equal to the number of persons in the circle, and k is the number of step to be taken for the next person.

#include <iostream>

using namespace std;

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

int main(){
    unsigned int n, k;
    cin >> n >> k;
    cout << f(n, k) << endl;
}

As you can see the algorithm works, but I would like to know how it works, I did not understand how it arrives at the final result.

My problem is with f(n, k) = (f(n-1, k) + k-1)%n + 1), I wonder how this can return the value corresponding to the last person left alive in the circle. I would also like to know what each return value of f(n-1, k) each recursion means, because for me the only one that makes sense is the last one, which is the final result.

Answer 1

The value of f(n-1, k) is the position of the person to be saved with one less person, i.e., the solution of the previous problem.

Example in Ideone

The program makes the calculations of the problem, starting from the simplest problem until the final problem.

Basically, the solution to the problem is a sequence of consecutive odd numbers, which goes back to 1 at all times that the number of persons in the circle is a power of 2.

The sequence of results is [1(1), 1(2), 3(3), 1(4), 3(5), 5(6), 7(7), 1(8), 3(9), 5(10)...]

But that sequence is only when k = 2. To k > 2 the sequence is different.

Answer 2

I haven’t circled the example I won’t claim to be right or not, but let’s talk quickly about recursion. I think that’s the problem with understanding. When you make a recursive call the function checks whether the result can be found or whether to make a new call. If you make a new call the system pushes the previous call, it is the same as when function A calls function B, A waits for the return of B to continue running. Only in the case of recursion the call is for the same function. When the value reaches 1 it is returned and the previous call can be calculated and also returns its result to the previous one. This happens successively until you arrive at the initial call that returns the value for printing.