时间戳

首页 > 解决方案 > 将 Log2 Iterativ 转为 Recursiv 方式

java - 将 Log2 Iterativ 转为 Recursiv 方式

问题描述

我想到了一个简单的任务，它以迭代方式计算 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

标签： javarecursion

解决方案

您忘记了在每个递归级别累积值。粗略的解决方案（我没有检查它是否存在错误）可能是：

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

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

推荐阅读