java - 在递归计算幂时我不理解我的方法的输出

Question

当我尝试递归计算 2^8 时，我没有看到如何使用此方法 31 次。

此方法是否以 O(logN) 复杂度计算幂？

当我运行它时，输出是:

0
1
2
3
4
5
...
29
30
2^8 is: 256

代码

private static int power(int x, int y)
{
    System.out.println(step++);

    if (y == 0)
        return 1;

    return power(x, y/2) * power(x, y/2);
}

Answer 1

这里实际上是用相同的值对 power 方法进行了两次调用:

return power(x, y/2) * power(x, y/2);

相反，如果您这样写，您可以进行一半的调用:

int toReturn = power(x, y/2);
return toReturn * toReturn;

如果我们遍历您的原始示例，我们将进行 31 次调用，这就是您所看到的(0 到 30)。遍历您的代码以了解原因:

power(2, 8)

power(2, 4)
power(2, 4)

power(2, 2)
power(2, 2)
power(2, 2)
power(2, 2)

power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)
power(2, 1)

power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)
power(2, 0)