递归地反转数组中的元素

Question

我想在JavaScript中编写一个递归函数，该函数返回一个数组，其元素反转。此代码生成以下错误：

未定义不是函数

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

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

数组的反向是（1）为空（如果为空）；否则为0。（2）否则，将头添加到尾巴反面的末端的结果。

不幸的是，即使在提供优化尾部递归的JS实现中（此时恰好没有），在这种情况下也不会应用它，因为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, []);
}

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