gistfile1.java

package recursionwachs;
public class Main {

    // runs in O(n). Accesses ruler array elements contiguously for optimal speed
    public static void computeTicksIterative(int[] ruler) {
        for (int i = 0; i < ruler.length-1; i++) {
            ruler[i] = bitToI[Integer.lowestOneBit(i)%37];
        }
    }

    // recursive algorithm to compute ruler ticks
    public static void computeTicksRecursive(int[] ruler, int start, int end, int n) {
        // do nothing in the base case
        if (n == 0) return;

        // this is the length of the two 'sub-rulers' we will split the ruler into
        int halfOfRuler = (end-start-1)/2;

        // set the middle tick value
        int i = start + halfOfRuler + 1;
        ruler[i] = n;

        // the first sub ruler (half length of current ruler)
        computeTicksRecursive(ruler, start, start + halfOfRuler, n - 1);

        // second sub-ruler
        computeTicksRecursive(ruler, start + halfOfRuler + 1, end, n-1);
    }

    // output ticks for a ruler of length `length`. Set recursive to true for
    // recursive algorithm - otherwise iterative is used.
    public static void outputTicks(int length, boolean recursive) {
        // find n, and allocate the ruler array
        int n = (int)Math.round(Math.log10(length)/Math.log10(2));
        int[] ruler = new int[length+1];

        // use the user-preferred algorithm to write ticks to the ruler array
        if (recursive) {
            computeTicksRecursive(ruler, 0, length, n);
        } else {
            computeTicksIterative(ruler);
        }

        // output ticks to console
        for (int tick : ruler) {
            System.out.print(tick);
        }
        System.out.println();

        // output indices to console
        for (int i = 0; i <= length; i++) {
            System.out.print(i%10);
        }
        System.out.println();
    }

    // takes in integer mod 37 with one bit set, returns which bit it is
    static int[] bitToI;

    public static void main(String[] args) {
        // initialize lookup table
        bitToI = new int[37];
        int k = 1;
        for (int i = 0; i < 30; i++) {
            bitToI[k%37] = i+1;
            k <<=1;
        }
        outputTicks(64, true); // uses recursive algorithm
        outputTicks(64, false); // uses iterative algorithm
    }

}