将Log2迭代变为递归

Question

我想到了一个简单的任务，即以迭代的方式计算Log2，如:

public static int log2(int x) {
int result = 0;
while (x > 1) {
x = x / 2;
result++;
}
return result;
}

现在我想把它变成递归函数，但我觉得我把它弄得太复杂了

像这样结束:

public static int recLog2(int x) {
if (x < 1) {
return x;
} else {
return recLog2(x/2);
}
}

问题是我走得太远了，我不知道如何得到它的答案。

的例子:

log2(13) -> 3
reclog2(13) -> 1 

Answer 1

您忘记在每个递归级别累积值。粗略的解决方案(我没有检查它是否有偏离1的错误)可能是:

if (x < 1) {
return 0;
} else {
return 1 + recLog2(x/2);
}

似乎是学习的例子，所以我把最后的解决方案留给你。如果是出于实际目的，我建议使用基于Java方法Integer.numberOfTrailingZeros(Integer.highestOneBit(x))构建的表达式，这样更简洁、更高效。