javascript - 在javascript中实现递归反向函数

Question

我正在尝试编写一个反转列表的函数。该函数是递归的。

我知道 javascript 没有 TCO，但我还是想试验一下:

reverse = function(list) {
    if (list.length < 2) { return list }
    fk = fork(list);
    return reverse(fk.tail).concat([fk.head])
}

fork 函数将列表拆分为头部和尾部:

fork = function(list) {return {head: list[0], tail: list.slice(1)}}

当我用列表 [1,2,3,4,5] 调用 reverse() 时，我得到了这个结果:

reverse([1,2,3,4,5]) // [5,4,4,4,4]

不确定我在这里做错了什么。预期结果是 [5,4,3,2,1]。

请帮忙。

Answer 1

您应该对代码进行 lint，这会对您有很大帮助。特别是，此代码失败，因为 fk 被视为全局变量。如果您在它前面加上 var，它会起作用:

var reverse = function(list) {
    if (list.length < 2) { return list }
    var fk = fork(list);
    return reverse(fk.tail).concat([fk.head])
}

就目前而言，在每次递归调用中，您修改相同的 fk 变量，本质上意味着连接相​​同的 fk.head - 最后一个元素之前的元素。

---

事实上，你在这里甚至不需要临时变量:

function recursive_reverse(list) {
  return list.length < 2 ? list : recursive_reverse(list.slice(1)).concat([list[0]]);
}

---

至于尾递归，这里有一种可能的方法:

function recursive_reverse(list) {
  return tail_recursive_reverse(list, []);
}

function tail_recursive_reverse(list, res) {
  if (!list.length) return res;
  var head = list[0];
  var tail = list.slice(1);
  res.unshift(head);
  return tail_recursive_reverse(tail, res);
}