Filtering out neighboring ascending digits in quaternary numeral system
We are dealing with a runtime upperbounded by something like 4^n here.

If you are building a list of strings anyway, why not reuse the list of valid strings in the list and append these values to a digit to get a new value? 

public static void calculateQuarternary(int n) {

    int startPtr, endPtr;
    startPtr = endPtr = 0;

    ArrayList&lt;String&gt; alTemp = new ArrayList&lt;String&gt;();
    ArrayList&lt;String&gt; alCurrent = new ArrayList&lt;String&gt;();

    alCurrent.add("0");
    alCurrent.add("1");
    alCurrent.add("2");
    alCurrent.add("3");


    for (int i = 1; i &lt; n; ++i) {

        endPtr = alCurrent.size();
        alTemp.clear();

        for (int j = 0; j &lt; endPtr; ++j) {

            for (int k = 0; k &lt; 4; ++k) {
                if (shouldAdd(alCurrent.get(j), k)) {
                    alTemp.add(k + alCurrent.get(j) + "");
                }
            }
        }

        alCurrent = new ArrayList&lt;String&gt;(alTemp);
    }
    System.out.println(alCurrent.size());
}

public static boolean shouldAdd(String s, int k) {

    int firstChar = (int)(s.charAt(0) - 48);
    return k + 1 != firstChar;
}