c - 这个用于查找 Josephus 数的 C 代码如何工作？

Question

我正在编写计算约瑟夫斯数的代码。我只是在试验这些数字以使代码正确。这是我写的代码:

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

这是正确的(我总是保持k = 0)，但现在我不知道为什么。

我尝试手动追踪它，但没有得到相同的答案。

我认为它是这样工作的:

answer(2,0) => ((answer(1,0))+1)%3 => ((((answer( 0,0))+1)%2)+1)%3 => ((1%2)+1)%3 => (1+1) %3 => 2。

然而，答案是1。

有人可以解释一下吗？

Answer 1

• 往下走:

answer(2,0) => 返回 ((answer(1,0))+1)%2 + 1

answer(1,0) => 返回 ((answer(0,0))+1)%1+ 1

answer(0,0) => 返回 0

• 上去:

answer(1,0) => 返回 (0+1)%1+ 1 即 1

answer(2,0) => 返回 (1+1)%2 + 1 即 1