在递归计算功率时,我不理解我的方法的输出

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)