javascript - 递归地反转数组中的元素

Question

我想用 javascript 编写一个递归函数，它返回一个元素反转的数组。此代码生成以下错误:

undefined is not a function

function reverseArray (toBeReversed){
  var reversed = [];

  function reverser (toBeReversed){
    if (toBeReversed.length == 1)
      reversed.push(toBeReversed[0]);
    else {
      reversed.push(toBeReversed.lastOfIndex(0)); //error on this line
      reverser(toBeReversed.slice(-1));
    }
  }

  reverser(toBeReversed);
  return reversed;
}

Answer 1

一个经典的递归实现是

function reverse(a) {
    if (!a.length) return a;
     return reverse(a.slice(1)).concat(a[0]);
}

您不需要任何循环、数组累积值、函数内的函数或任何其他机制。

如果您更喜欢编写少量单行代码以使您的代码更具可读性，那么

function head(a)    { return a[0];         }
function tail(a)    { return a.slice(1);   }
function push(a, v) { a.push(v); return a; }
function empty(a)   { return !a.length;    }

function reverse(a) { 
    if (empty(a)) return a;
    return push(reverse(tail(a)), head(a)); 
}

这个小程序具有可以被“阅读”为英文的特性，我认为更多的程序应该具有这一特性。在这种情况下是

The reverse of an array is (1) empty, if it is empty; (2) otherwise, the result of adding the head to the end of the reverse of the tail.

不幸的是，即使在提供优化尾递归的 JS 实现中(此时恰好是 none)，它也不会在这种情况下应用，因为 JS 必须保留堆栈以调用 concat 每次 reverse 的结果。我们可以写一些可优化的东西吗？是的，通过携带另一个值，即到目前为止反转数组的结果:

function unshift(a, v) { a.unshift(v); return a; }

function reverse(a) { return _reverse(a, []); }

function _reverse(a, result) {
    if (empty(a)) return result;
    return _reverse(tail(a), unshift(result, head(a)));
}

如果你愿意

function reverse(a) { 
    return function _reverse(a, result {
        if (empty(a)) return result;
        return _reverse(tail(a), unshift(result, head(a)));
    }(a, []);
}

这不是很干净，但给我们带来的好处是仍然能够思考递归，而没有与递归相关的正常堆栈开销。