When to use ArrayList over array in recursion

Question

So I have this problem. I was trying to code a program to print all the valid possible arrangements of brackets i.e. for 3 brackets we can have ((())), (()()), ()()(), (())() etc.

I have a working code

public static void main(String[] args) {
    int number = 3; // No. of brackets
    int cn = number;
    int on = number;
    // open and closed brackets respectively
    char[] sol = new char[6];
    printSol(on, cn, sol, 0);
}

public static void printSol(int cn, int on, char[] sol, int k) {
    if (on == 0 && cn == 0) {
        System.out.println("");
        for (int i = 0; i < 6; i++) {
            System.out.print(sol[i]);
        }
    }

    else {
        if (on > 0) {
            if (cn > 0) {
                sol[k] = '(';
                printSol(on - 1, cn, sol, k + 1);
            }
        }

        if (cn > on) {
            sol[k] = ')';
            printSol(on, cn - 1, sol, k + 1);
        }
    }
}

Now the problem is that I want to do this using ArrayList instead of using char array. I tried but am getting errors. If anyone has any suggestions please let me know. The main purpose of asking this question is that I want to know when shall I prefer ArrayLists over arrays in Recursion problems.

P.S. I am sorry for the poor indentation as I had to type the whole program due to surfing restrictions and also thre might be some syntax errors but I tried my best. Thanks Mohit

Answer 1

You want to avoid passing large data structures by-value while recursing as it can consume a lot of memory. That's about the only thing I can think of, in general. Passing a reference to an array or ArrayList is ok. I prefer ArrayList in general.

Look at Java's Stack class for this problem in particular.

Answer 2

I think you're doing just fine using char[]. It's quick and it's to the point.

I'd say most recursion problems you face in practice don't follow this pattern. That's because typically with problems demanding recursion you're performing a search on a search tree for one specific goal (one specific leaf node on a tree). You're performing iteration: you're trying to visit every leaf node on a tree, and perform an action for each.

With the common search algorithms (like a depth-first search), you thus wouldn't need to prepare the result as you recurse, but rather as you unwind, after you've found the goal.

But for cases where you do, char[] works great. You're basically simulating a stack through the parameters sol and k (sol holds the data while k points to the top of the stack). As others have noticed, you could use a stack directly (by passing a Deque<Character> implementation, commonly a LinkedList).

In my mind ArrayList is a step backwards. If you're going to use a collection, use one made for the problem.

Edit: Here's an untested implementation using a Deque instead:

public static void printSol(int cn, int on, Deque<Character> sol) {
    if (on == 0 && cn == 0) {
        System.out.println("");
        for ( Iterator<Character> it = sol.descendingIterator(); it.hasNext(); ) {
            System.out.println(it.next());
        }
    }

    else {
        if (on > 0) {
            if (cn > 0) {
                sol.push('(');
                printSol(on - 1, cn, sol);
                sol.pop();
            }
        }

        if (cn > on) {
            sol.push(')');
            printSol(on, cn - 1, sol);
            sol.pop();
        }
    }
}

//...
printSol(3, 3, new ArrayDeque<Character>(6));

As you can see, very few changes.

Edit 2: One thing we haven't discussed at all for this specific problem is StringBuilder.

StringBuilder is a mutable String type that allows you to easily append and remove characters. This would be a great solution for this problem as well:

public static void printSol(int cn, int on, StringBuilder sol) {
    if (on == 0 && cn == 0) {
        System.out.println(sol);
    }

    else {
        if (on > 0) {
            if (cn > 0) {
                sol.append('(');
                printSol(on - 1, cn, sol);
                sol.deleteCharAt(sol.length()-1);
            }
        }

        if (cn > on) {
            sol.append(')');
            printSol(on, cn - 1, sol);
            sol.deleteCharAt(sol.length()-1);
        }
    }
}

Answer 3

I realized nobody (including myself) actually answered your question. I think you've been convinced using an ArrayList isn't desirable here. But how could you make it work?

The easiest way is to basically fake a stack with it:

public static void printSol(int cn, int on, ArrayList<Character> sol) {
   //...
   sol.add('(');
   printSol(on - 1, cn, sol);
   sol.remove(sol.size() - 1);