Fill 2D array recursively

Question

I'm currently working through "Algorithms in java" by Robert Sedgewick (3rd edition, german version) on my own and I'm trying to solve one of the exercises there.

Problem Statement

The exercise asked to create an int[][] 2D array with \$2^n\$ rows in which each row stores the binary representation of its own index but using \$n\$ cells (so first cell is not always '1'). It also asks to do this recursively.

This can be done 2 ways:

1. By writing 2 different recursive methods. One, to access the first cell in each row where it starts and the second method to fill the row
2. By writing 1 recursive method that contains both recursions

My Thoughts

I deemed the second one to be more difficult and since I'm still struggling with recursion, I tried to solve the exercise using the harder approach in order to potentially learn more. I'd therefore also ask you to pay special attention to the recursive fill() and how it is written with that goal in mind. Below is my solution, but first an explanation how the fill method is intended to work.

My Solution

• The variable array is the 2D array that shall contain the binary representations of all numbers between \$0\$ and \$(2^n)-1\$.
• toBinary is a char[] of the Integer.toBinary(num) string. Each row has their own toBinary due to every row storing the binary representation of a different number.
• num is the number whose binary representation is stored in row 'num'
• array.numBinaryIndex is used to traverse the binary representation of num and fill the cells in row 'num'

Note: the '0's and '1's from toBinary of num are converted to int and copied over to array[num]. If toBinary.length of num != array[num].length=\$2^n\$ (e.g. toBinary.length = 1 for num = 1 and array[num].length = 8 for n=3), all cells from 0 to delta_Array_toBinary-1 shall be filled with 0.
Then, starting from array[num][delta_Array_toBinary], the rest of the row shall be filled with the contents of toBinary converted into int, starting from 0 to toBinary.length using numBinaryIndex - delta_Array_toBinary.

---

public class Aufgabe5_25 {
    static void fill(int[][] array, int num, int numBinaryIndex, char[] toBinary) {
        /*-
         * - End the recursion filling first cells in rows if the index (num) moves
         * past array.length
         * - End the recursion filling rest of the rows if the
         * index (numBinaryIndex) moves past array[num].length
         */
        if (num == array.length || numBinaryIndex == array[num].length) {
            return;
        }

        /*
         * Recursively fill all array[num][0] and start recursions to fill all
         * cells of array[num]
         */
        if (numBinaryIndex == 0) {
            toBinary = Integer.toBinaryString(num).toCharArray();

            if (toBinary.length == array[num].length) {
                array[num][0] = toBinary[0];
            } else {
                array[num][0] = 0;
            }

            /* Recursion to go to next row at array[num+1][0] */
            fill(array, num + 1, 0, toBinary);
        }

        /*
         * Is accessed after num == array.length happens, recursively fills the
         * rows for each recursion that has been started in the
         * if(numBinaryIndex == 0) part.
         */
        if ((array[num].length) - numBinaryIndex > toBinary.length) {
            array[num][numBinaryIndex] = 0;
            fill(array, num, numBinaryIndex + 1, toBinary);
        } else {
            int delta_Array_toBinary = (array[num].length - toBinary.length);
            /*-'0' to convert from char to int*/
            array[num][numBinaryIndex] = (toBinary[numBinaryIndex - delta_Array_toBinary] - '0');
            fill(array, num, numBinaryIndex + 1, toBinary);
        }
    }

    /*
     * Hides parameters needed to start recursion that have to be given as
     * null/0 in the beginning
     */
    static void fill(int[][] array) {
        fill(array, 0, 0, null);
    }

    static void printArray(int[][] array) {
        System.out.println("Final Print");
        for (int i = 0; i < array.length; i++) {
            System.out.print(i + ": ");
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        /*
         * Create 2D array of all numbers between 0 and 2^n (excluding 2^n) and
         * fill it.
         */
        int n = 4;
        int[][] array = new int[(int) Math.pow(2, n)][n];
        fill(array);

        /* Print 2D array for checking purposes */
        printArray(array);
    }
}

---

Final Statements

This does produce the intended results (checked for 2,3,4,5), but as you can see, this code seems bloated and not quite that readable. My questions are

1. Could this solution be written more concisely/elegantly bearing in mind earlier mentioned approach number 1 (meaning the reason it is this bloated is just due to me struggling with recursion still)?

2. In contrast, could one say that there is a lesson here that double-recursions should never be done using only 1 recursive method (meaning one should always use earlier mentioned approach number 2)?

Answer 1

I tried it myself but with only tail-recursion. (Meaning the recursive call is the last thing that is called inside the method). This resulted in the following code (based mostly on yours):

static void fill2(int[][] array, int num, int numBinaryIndex, char[] toBinary) {
    // All rows filled, we can stop.
    if (num == array.length) {
        return;
    }

    //reached the end of the row, start a new one
    if(numBinaryIndex==array[num].length){
        int newRowNum = num+1;
        fill2(array, newRowNum, 0, null);
        return;
    }

    //toBinary is null when a new row is started, so we have to initialise it first
    if(numBinaryIndex==0){
        toBinary = Integer.toBinaryString(num).toCharArray();
    }

    if ((array[num].length) - numBinaryIndex > toBinary.length) {
        array[num][numBinaryIndex] = 0;
    } else {
        int delta_Array_toBinary = (array[num].length - toBinary.length);
        /*-'0' to convert from char to int*/
        array[num][numBinaryIndex] = (toBinary[numBinaryIndex - delta_Array_toBinary] - '0');
    }
    //this was the same in both the if and else clause, might as well just put it after.
    fill2(array, num, numBinaryIndex + 1, toBinary);
    return;
}

This doesn't look any better than yours either :)

I tried to add a second index to keep track of where in array[num][?] we are so we can just skip the leading 0s (since default value for int is 0). But that quickly became unreadable for other reasons ...

Your conclusion is right that doing more than 1 thing inside a method is a bad idea. This actually applies to more than recursion. A rule of thumb is that when you have to place a comment inside a method to explain what a group of lines does, you should extract those lines in their own method with a good name that makes the comment obsolete.

---

As a side node: In java recursions are not so good. Because the java compiler has to keep all the calls on the stack meaning you will run out of memory fast. Your fill method for example can handle up to n = 13 on my current machine with default java settings.

I've written a variant using for loops instead of recursion:

static int[][] generateBinaryArray(int n){
    int[][] result = new int[(int) Math.pow(2, n)][n];
    for(int i = 0; i < result.length;i++){
        char[] binary = Integer.toBinaryString(i).toCharArray();
        for(int j = 1; j< binary.length+1; j++){
            result[i][result[i].length-j] = binary[binary.length-j]-'0';
        }
    }
    return result;
}

This has no problems with n up to 24 and get's stuck on garbage collection at n=25.

Other languages like scala can re-use the same memory in case of tail recursion (so like my fill2 variant). So in that case the recursion does work nicely.

---

Edit: Elaboration on static

Your use of static methods here is perfect here. Especially adding the second one that only takes the array to hide the internal implementation of how it's filled. The only thing I would change about this is adding public/private modifiers to the methods like so:

//this method is public, it's the one you call from another class to fill a new array 
public static void fill(int[][] array) {
    fill(array, 0, 0, null);
}

//this method is private. It should only be called by the other fill method
private static void fill(int[][] array, int num, int numBinaryIndex, char[] toBinary) {
    ...
}

By making the second method private you make it clear that it should only be called from inside the class as it is a helper method. The fact that we solve the filling with recursion is an implementation detail from this class that doesn't need to be exposed. If we ever want to change the implementation (for example to my for loop based one) we can do so without fear of breaking any other classes that might have called that method.

My point in the comment about avoiding static is about the following case:

public class MySolution {
    public static int[][] array = new int[0][0];

    public static void fill(){
        fill(0, 0, null);
    }

    private static void fill(int num, int numBinaryIndex, char[] toBinary) {
        ... your implementation but without the array passed to it
    }
}

Note that this is good enough if you just want to try your fill implementation as a solution for that exercise.

Normally that static variable (especially public!) is not done.

We can still get around the public variable by doing the following:

public class MySolution {
    private static int[][] array = new int[0][0];

    public static void fill(array){
        this.array = array;
        fill(0, 0, null);
    }

    private static void fill(int num, int numBinaryIndex, char[] toBinary) {
        ... your implementation but without the array passed to it
    }
}

But using this static variable so you don't have to pass it as a parameter will get you into all sorts of trouble in a multi-threaded program.

If you want to have a properly designed solution I suggest something like follows (but again, it's overkill for solving a simple exercise).

/**
* A class that parses a number into it's binary representation.
* It even has a documentation comment explaining what it does.
*/
public class BinaryParser {
    private int[][] array; //TODO change this name to something more meaningful

    /**
    * Creates a new parser with the expected digits in the binary number.
    */
    public BinaryParser(int size){
        array = new int[(int) Math.pow(2, size)][size];
    }

    //This is only a helper method for the implementation. 
    //No other class needs to know about it so we make it private. 
    private void fill(int num, int numBinaryIndex, char[] toBinary){
        ... again your implementation, but now using the internal array from the object
    }

    /**
    * Returns the binary representation of the number as a string 
    */
    public String parse(int number){
        //TODO test this implementation, I just guessed one :)
        return Arrays.toString(array[number]);
    }

    /**
    * A helper method that prints all available numbers with their binary representation
    */
    public void prettyPrint(){
        System.out.println("Final Print");
        for (int i = 0; i < array.length; i++) {
            System.out.println(i + ": " + parse(i));
        }
    }

    public static void main(String[] args) {
        BinaryParser parser = new BinaryParser(4);
        parser.prettyPrint();
    }
}

Important thing to note here is that we no longer expose that it's implemented with an array. So if we ever want to change the implementation of the parser we can safely do so without worrying about braking other code. We encapsulate all the implementation details inside this class.