Filtering out neighboring ascending digits in quaternary numeral system Take in a natural number n ∈ N, then process and output a(n), with a(n) being the number of quaternary strings (with 0, 1, 2, 3) of length n, where (from left to right) there never follows a character (i + 1) directly after the character i.
  
  For example, n=3 results in a(3) = 42: 000, 002, 003, 020, 021, 022, 030, 031, 032,
  033, 100, 102, 103, 110, 111, 113, 130, 131, 132, 133, 200, 202, 203,
  210, 211, 213, 220, 221, 222, 300, 302, 303, 310, 311, 313, 320, 321,
  322, 330, 331, 332, 333.


How can performance be improved? n = 13 already takes 4 seconds.

import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.Scanner;

public class Quaternary {

    public static void start(){
        Scanner reader = new Scanner(System.in).useLocale(Locale.US);
        System.out.print("Enter number n: ");
        int n = Integer.parseInt(reader.nextLine());
        List&lt;String&gt; stringList = new ArrayList&lt;String&gt;();

        long startTime = System.nanoTime();

        for (int k=0; k &lt; 4; k++){
        findString(n, k, "", stringList);
        }

        System.out.println(“Number of strings with n = " + n +  " : "+ stringList.size());

        long estimatedTime = System.nanoTime() - startTime;
        double time = (double)estimatedTime / 1000000000.0;
        System.out.println(time);
    }

    public static void findString(int n, Integer lastNumber, String string, List&lt;String&gt; stringList)
    {
        string += lastNumber.toString();

        if (string.length() == n)
        {
            stringList.add(string);
        }
        else {
            for (int i = 0; i &lt; 4; i++)
            {
                if (i != lastNumber+1)
                {
                    findString(n, i, string, stringList);
                }
            }
        }
    }


    public static void main(String[] args) {
        start();
    }
}
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;
}