将递归转换为(for,while)循环

您不需要任何循环来计算结果。当您为您编写第一个值时，Q(...)您会看到一个模式，其中相同的术语被取消，因为您将Q(x) ^ Q(x)在某个时候运行类似的东西，结果是0. 检查以下列表中Q(...)的第一个数字：

Q(1) = a
Q(2) = b
Q(3) = Q(2) ^ Q(1) = a^b
Q(4) = Q(3) ^ Q(2)
= Q(2) ^ Q(1) ^ Q(2)
= Q(1) = a
Q(5) = Q(4) ^ Q(3)
= Q(1) ^ Q(2) ^ Q(1)
= Q(2) = b
Q(6) = Q(5) ^ Q(4)
= Q(2) ^ Q(1) = a^b
Q(7) = Q(6) ^ Q(5)
= Q(2) ^ Q(1) ^ Q(2)
= Q(1) = a
Q(8) = Q(7) ^ Q(6)
= Q(1) ^ Q(2) ^ Q(1)
= Q(2) = b
Q(9) = Q(8) ^ Q(7)
= Q(2) ^ Q(1) = a^b


如您所见，该值在a,b和之间迭代a^b。因此，您可以使用简单的模检查q来获得正确的值：

public static long Q(long a,long b,long q){
long modulo = q%3;
if (modulo == 0) {
return a^b;
}
if (modulo == 1) {
return a;
}
return b;
}