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

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

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

不知道我在这里做错了什么.预期的结果是[5,4,3,2,1].

请帮忙.

Answer 1

你应该提取代码,这对你有很大的帮助.特别是,此代码失败,因为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);
}