Merge/multiply 个数组中的元素使用线性递归

Question

我必须实现一个递归方法 merge(long[] arr, int i)，如果相邻元素具有相同的值，则将它们相乘，从索引 i 开始。示例：

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

应该生成这样的数组：

{1, 4, 4}

如果一个数字 {1, 2, 2, 2, 2, 5} 出现多次 (n) 次，则必须将所有这些相乘：{1, 16, 5}.

已经合并的号码不能再合并{1, 4, 4, 16} -> {1, 16, 16}.

所有这一切都必须通过使用仅此一种方法合并并对原始数组中的每个元素进行一次递归调用来实现。

这是一个使用递归和循环的有效实现：

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
        }
    }

此实现产生了正确的结果，但是递归深度错误（需要对原始数组 ns[] 中的每个元素进行一次递归调用）。

我敢肯定这里有一个天才可以使用线性递归解决这个问题。

Answer 1

让我们将循环转换为递归调用。这样做的唯一原因是作业要求它 - 它不是更具可读性（至少对我而言），而且它实际上更慢。出于效率原因，人们通常希望朝另一个方向前进：从递归到循环。

首先，您的代码的注释版本：

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!
}

首先，让我重写一下以提高效率。由于重复项只有在彼此相邻时才会被删除，因此您不需要内部循环，而是可以这样写：

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);
}

假设这可行（注意——我还没有测试过），我现在将把它转换成尾递归。将有两部分：驱动程序代码（不在循环中的所有内容）和递归代码（循环部分）。

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);     
}

总体思路是将所有状态作为参数传递给你的递归函数，并在开始时检查循环终止，将循环代码放在中间，最后，为下一次迭代进行递归调用.

Merge/multiply 个数组中的元素使用线性递归

Merge/multiply elements in Array using linear recursion

java

arrays

algorithm

recursion

long-integer