java - 将迭代函数转换为递归函数

Question

java version "1.8.0_92"

嗨，

我正在尝试将这个使用迭代的函数转换为递归函数。

  public static String bitConversion(int x) {
        List<Integer> binaryList = new ArrayList<Integer>();

        while(x > 0) {
            binaryList.add(x % 2);
            x /= 2;
        }

        StringBuilder stringBuilder = new StringBuilder();
        for(Integer binary : binaryList) {
            stringBuilder.append(binary.toString());
        }

        return stringBuilder.toString();
    }

我的尝试是这样的

  public static String bitConversion(int x) {
        List<Integer> binaryList = new ArrayList<Integer>();

        if(x <= 0) {
            StringBuilder stringBuilder = new StringBuilder();
            for(Integer binary : binaryList) {
                stringBuilder.append(binary.toString());
            }

            return stringBuilder.toString();
        }
        else {
            binaryList.add(x % 2);
            return bitConvert(x / 2);
        }
    }

有一件事是我需要有二进制列表来添加整数。在第一个条件下，当一切都完成后，我需要将它们放入字符串构建器中。在第二种情况下，我需要将它们添加到列表中。因此列表对于这两种情况都需要是全局的。但当函数调用自身时，列表每次都会重新初始化。

能否提供有关编写此递归函数的最佳方法的建议？

非常感谢您的建议。

Answer 1

基本上，对于递归，你有两个部分:1)递归终止条件2)将手头的任务分割成更小的部分，然后组合它们的结果。

public static String bitConversion(int x) {
    // just simplifying my life here as negative numbers can be represented
    // in a few ways and usually it's additive code I don't want to deal
    // with here :)
    if (x < 0) {
        throw new IllegalArgumentException("Not implemented for negatives");
    }

    // recursion termination condition for 0 and 1
    if (x <= 1) {
        return String.valueOf(x);
    }

    // recurision
    int leastSignificantBit = x % 2;
    String significantBits = bitConversion(x / 2);
    return significantBits + leastSignificantBit;
}