java - 算二元递归吗？

Question

编写一个 countBinary 方法，该方法接受整数 n 作为参数，并按升序打印具有 n 位数字的所有二进制数，并将每个值打印在单独的行上。所有数字均应显示所有 n 位数字，必要时包括前导零。您可以假设 n 是非负数。如果 n 为 0，则应生成一个空行输出。不要在解决方案中使用循环；递归地实现它。

我遇到的问题是我不知道如何打印零和一，因为 n 是我可以拥有的唯一参数。我也无法使用 for 循环并将递归调用放入循环中，所以我有点卡住了。这是我到目前为止所拥有的:

    public static void countBinary(int n){
if (n < 0) {
    throw new IllegalArgumentException();
}if(n == 0){
    System.out.print("");
}else{
    countBinary(n - 1);
    System.out.println(n ); // I tried doing n + "0" and + "1" did not work
    countBinary(n - 1 );
    System.out.print(n );
   // store += n;

}

}

这是我的 countBinary(2) 输出:

    1
   12
    1
   12

什么时候应该是这样:

   00
   01
   10
   11

我为其他每一行都获得了正确数量的“级别”，这很奇怪，但我真的被卡住了

注意:这不是作业，只是练习。谢谢!

Answer 1

你走在正确的轨道上，递归了两次。概念是打印“0”后跟一个 (n-1) 位数字，然后打印“1”后跟一个 (n-1) 位数字数字。诀窍是弄清楚如何处理这样一个事实:对于 n > 1，有许多 (n-1) 位数字，并且每个数字都需要具有“0”或“1”在他们前面。处理这个问题的方法是不实际打印“0”或“1”，而是将其向下递归传递，直到准备好打印每一整行。为此，您需要一个辅助方法来执行实际的递归，您可以使用 char[]、StringBuilder 甚至 String 到目前为止待处理的输出。 (我会使用第一个，第二个也很好。我会避免使用 String 因为每次需要添加“时它都会生成一个新的 String 0”或“1”——很多垃圾。)

这是我的解决方案:

public static void countBinary(int n){
    if (n < 0) {
        throw new IllegalArgumentException();
    }
    countBinary(new char[n], n);
}

private static void countBinary(char[] prefix, int n) {
    if (n == 0) {
        // base case -- no more recursion
        System.out.println(prefix);
    } else {
        // position next digit counting from the right so output is in increasing order
        final int i = prefix.length - n;

        // prefix a '0' and recurse
        prefix[i] = '0';
        countBinary(prefix, n-1);

        // prefix a '1' and recurse
        prefix[i] = '1';
        countBinary(prefix, n-1);
    }
}