CODEWITHSUNDEEP
javascriptrecursion
dopatraman
dopatraman

Reputation: 13908

implementing a recursive reverse function in javascript

I'm trying to write a function that reverses a list. The function is recursive.

I know javascript does not have TCO, but i wanted to experiment with this anyway:

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

the fork function splits a list to a head and a tail:

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

When I call reverse() with the list [1,2,3,4,5], I get this result:

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

Not sure what I'm doing wrong here. The expected result is [5,4,3,2,1].

Please help.

Upvotes: 1

Views: 249

Answers (1)

raina77ow
raina77ow

Reputation: 106453

You should lint your code, that'll help you tremendously. In particular, this code fails because fk is treated as a global variable. If you prefix it with var, it works:

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

As it stands now, at each recursive call you modify the same fk variable, essentially meaning concating the same fk.head - the element before the last one.

In fact, you don't even need temporary variable here:

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

As for tail recursion, here's one possible approach:

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

Upvotes: 5

Related Questions