将迭代函数转换为递归

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);
        }
    }

有一件事是我需要使用binaryList来添加Integer.在完成所有事情的第一个条件中,我需要将它们放入一个字符串构建器中.在第二个条件中,我需要将它们添加到列表中.所以List必须是全局的两种条件.但是当函数调用自身时,每次都会重新初始化List.

关于编写这种递归函数的最佳方法有什么建议吗？

非常感谢任何建议.

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;
}