Merge/multiply elements in Array using linear recursion

Question

I must implement a recursive method merge(long[] arr, int i) which multiplies adjacent elements if they have the same value, starting at index i. Example:

merge({1, 2, 2, 4}, 0)

should produce an array like this:

{1, 4, 4}

If there are multiple (n) occurrences of a number {1, 2, 2, 2, 2, 5}, all of these must be multiplied together: {1, 16, 5}.

A number which has already been merged can not be merged again {1, 4, 4, 16} -> {1, 16, 16}.

All this must be achieved by using only this one method merge and having exactly one recursive call per element in the original array.

This is a working implementation using recursion and loops:

public static long[] merge(long[] ns, int i) {
    final long[] EMPTY_LONG_ARRAY = {};
    if (i < 0) {
        return merge(ns, 0, m); // if i negative, start at 0
    } else if (i >= ns.length) {
        return EMPTY_LONG_ARRAY; // if out of bounds, return empty array
    } else if (i == ns.length - 1) {
        return ns; // base case
    } else { // recursion in here
        if (ns[i] == ns[i + 1]) { // if next long is equal
            int occurences = 1; // first occurence
            for (int j = i; j < ns.length - 1; j++) {
                if (ns[j] == ns[j + 1])
                    occurences++;
                else
                    break;
            } // add next occurences
            long[] newArray = new long[ns.length - occurences + 1]; // new array is (occurences-1) shorter
            for (int j = 0; j < newArray.length; j++) { // fill new array
                if (j < i) {
                    newArray[j] = ns[j]; // left of i: values stay the same
                } else if (j > i) {
                    newArray[j] = ns[j + occurences - 1]; // pull values right of i (occurences-1) to the left
                } else {
                    int counter = occurences;
                    long mergedValue = ns[j];
                    while (counter > 1) {
                        mergedValue *= ns[j];
                        counter--;
                    }
                    newArray[j] = mergedValue; // at j: value is ns[j]^occurences
                }
            }
            if (i == ns.length - 1)
                return merge(newArray, i, m);
            else
                return merge(newArray, i + 1, m); // if bounds permit it, jump to next number
        } else {
            return merge(ns, i + 1, m); // nothing to merge, go one step forward
        }
    }

This implementation produces the correct result, however, the recursion depth is wrong (needs to be one recursive call per element in original array ns[]).

I'm sure there is a genius out here who can solve this using linear recursion.

Answer 1

Lets transform your loop into a recursive call. The only reason to do this is that the assignment asks for it - it is not more readable (at least to me), and it is actually slower. People usually want to go in the other direction for efficiency reasons: from recursion to loops.

First, an annotated version of your code:

public static long[] merge(long[] ns, int i) { // i not needed, but useful for recursion
    long[] out = new long[ns.length];          // for result; allocate only once
    for (int j = i; j < ns.length; j++) {      // main loop, condition is "j == length"
        int occurences = 0;
        for (int k = i; k < ns.length; k++) {  // inner loop - can avoid!
            if (ns[j] == ns[k]) {
                occurences++;
            }
        }
        out[j] = (long) Math.pow(ns[j], occurences); // updating the result
    }
    // remove additional elements
    return out; // this does not remove elements yet!
}

First, let me rewrite that to be more efficient. Since duplicates are only removed if they are next to each other, you do not need the inner loop, and can write this instead:

public static long[] merge(long[] ns) {
    long[] out = new long[ns.length];
    int oSize = 0;     // index of element-after-last in array out
    long prev = ns[0]; // previous element in ns; initial value chosen carefully
    out[0] = 1;        // this make the 1st iteration work right, not incrasing oSize
    for (int i=0; i<ns.length; i++) {
        long current = ns[i];
        if (current == prev) {
           out[oSize] *= current;   // accumulate into current position
        } else {
           oSize ++;                // generate output
           out[oSize] = current;    // reset current and prev
           prev = current; 
        }
    }
    // generate final output, but do not include unused elements
    return Arrays.copyOfRange(out, 0, oSize+1);
}

Assuming this works (and beware - I have not tested it), I will now transform it into tail recursion. There will be 2 parts: a driver code (everything not in the loop), and the recursive code (the loopy part).

public static long[] merge(long[] ns) {
    long[] out = new long[ns.length];
    int oSize = 0;     
    long prev = ns[0]; 
    out[0] = 1;        
    int i=0;           
    recursiveMerge(ns, i, out, oSize, prev);  // recursion!
    return Arrays.copyOfRange(out, 0, oSize+1);
}

public static void recursiveMerge(long[] ns, int i, long[] out, int oSize, long prev) {

    if (i == n) return; // check "loop" termination condition
    
    // copy-pasted loop contents
    long current = ns[i];
    if (current == prev) {
        out[oSize] *= current;   // accumulate into current position
    } else {
        oSize ++;                // generate output
        out[oSize] = current;    // reset current and prev
        prev = current; 
    }
 
    // next loop iteration is now a recursive call. Note the i+1
    recursiveMerge(ns, i+1, out, oSize, prev);     
}

The general idea is to pass all state as arguments to your recursive function, and check loop termination at the start, put the loop code in the middle, and at the very end, make a recursive call for the next iteration.